7
$\begingroup$

Which is larger, $99^{100}$ or $100^{99}$?

Which is larger, $999^{1000}$ or $1000^{999}$?

Or more generally, for $n$ any natural number: which is larger, $n^{n+1}$ or $(n+1)^n$?

Please do not use a computer, calculator, or any electronic aid to work out the answer for any specific cases of $n$. You should be able to solve this puzzle purely by mathematical reasoning and without calculations, using a computer only to read the question and type the answer :-)

$\endgroup$
  • 7
    $\begingroup$ I think the math methods needed to solve this are too standard for this to be an interesting puzzle. $\endgroup$ – xnor Jul 8 '15 at 1:03
  • 1
    $\begingroup$ I respectfully disagree with xnor -- I thought the connection needed to solve the puzzle was interesting and unexpected. Thanks for posting! $\endgroup$ – Tyler Seacrest Jul 8 '15 at 5:38
  • $\begingroup$ It's easy for people like me and @xnor who have lots of advanced maths knowledge, but interesting for those who don't. Maybe xnor is just sore he didn't get to this one first? :-) $\endgroup$ – Rand al'Thor Jul 8 '15 at 8:42
  • $\begingroup$ How are we to compare their pixel size to see which is larger without the use of computers?! You are a madman! $\endgroup$ – Mark N Jul 8 '15 at 12:57
15
$\begingroup$

$n^{(n+1)}$ is larger iff $n\geq 3$

$$n^{(n+1)} > (n+1)^n \\n > \left(\frac{n+1}{n}\right)^n \\n > \left(1+\frac 1 n\right)^n$$

The right side increases with $n$, and we know that

$$\lim_{n\to\infty}\left(1+\frac 1 n\right)^n=e$$

Therefore, for $n\geq 3$,

$$n > e > \left(1+\frac 1 n\right)^n$$

Now we only have to check $n=2$ and $n=1$ by hand.

$$2^3 < 3^2\\1^2 < 2^1$$

$\endgroup$
  • $\begingroup$ Very good. This is what I was looking for! $\endgroup$ – Rand al'Thor Jul 8 '15 at 8:43
  • 2
    $\begingroup$ @2012rcampion - could you explain to me how you get from the first line to the second in your work? $\endgroup$ – Nyk 232 Jul 8 '15 at 13:58
  • 1
    $\begingroup$ @Nyk232 You divide by $n^n$ on both sides. $\endgroup$ – mmking Jul 8 '15 at 14:14
  • $\begingroup$ @mmking ahh, I see now. thanks for letting me know! $\endgroup$ – Nyk 232 Jul 8 '15 at 14:15
5
$\begingroup$

Asking which of $x^y$ or $y^x$ is bigger is the same as asking which of their logs is bigger, so what comparison sign should fill the blank in $$ y\log x\,\,\,\_\,\,\,x\log y? $$ Rearranging, this becomes $$ \frac{\log x}{x}\,\,\,\_\,\,\,\frac{\log y}y $$ So, letting $f(t)=\frac{\log t}t$, is $f(x)$ or $f(y)$ bigger? Looking at the graph of f(t), we see that $f$ is increases up to a point, then decreases thereafter. To find this point, we compute the derivative $f'(t)=\frac{1-\log t}{t^2}$, then set this to zero, so the maximum of $f$ occurs at $t=e$. In summary:

$x^y-y^x$ has the same sign as $f(x)-f(y)$, which is negative when $x<y<e$, and positve when $e<x<y$.

In our case, we see that $n^{n+1}-(n+1)^n$ will be positive when $n\ge3$, so for almost all $n$, $n^{n+1}>(n+1)^n$.

$\endgroup$
  • 5
    $\begingroup$ I think "looking at the graph" counts as using a computer... but it's very easy to show that $f(t)$ is only increasing when $$f'(t)>0\\\frac{1-\log t}{t^2}>0\\1-\log t>0\\\log t<1\\t<e$$ (for positive $t$). $\endgroup$ – 2012rcampion Jul 8 '15 at 3:12
  • $\begingroup$ @2012rcampion very good points! $\endgroup$ – Mike Earnest Jul 8 '15 at 3:14
  • $\begingroup$ Another interesting approach, +1 $\endgroup$ – Rand al'Thor Jul 8 '15 at 8:43
  • $\begingroup$ @2012rcampion Graph scetching does not need a computer. Also you should not really need to look at the graph of log(t)/t to see that it will increase up to a point maximum and then turn. $\endgroup$ – Taemyr Jul 8 '15 at 11:22
2
$\begingroup$

The question said no calculations as well as no calculators, so here is my answer with the fewest calculations I could manage.

Ask another question: Which pair is going to be closer,

$99^{100}$ and $100^{99}$

or,

$999,999^{1,000,000}$ and $1,000,000^{999,999}$?

99 is almost 100 only a bit smaller, so doing another multiplication is making a number that is a bit smaller an other 100 times larger.

999,999 is much closer to a million that 99 is to 100 so the effect of raising an extra power will be much closer to multiplying by an extra million adding 6 zeros.

Clearly $n$ being larger favours $n^{n+1}$ to be the greater of the two.

So how small does $n$ have to be for $n^{n+1}$ to be smaller.

$1^{2} - 2^{1} = 1 - 2 = -1$
$2^{3} - 3^{2} = 8 - 9 = -1$
$3^{4} - 4^{3} = 81 - 64 = 17$

Looks like $n^{n+1}$ is biggest when...

n > 2

Negative values of $n$ exhibit the switching of sign expected for multiplying negative numbers, so there is a different rule, but that is left as an exercise, as the question only asked for natural numbers (positive whole numbers).

$\endgroup$
  • $\begingroup$ Even 81-64 is a bigger calculation than anyone else had to do. I don't agree that this involves less calculation than the other answers. $\endgroup$ – Rand al'Thor Jul 8 '15 at 8:44
  • 1
    $\begingroup$ @randal'thor But you don't need to calculate that, you only need to see that 81 is larger than 64, and that's trivial. $\endgroup$ – Dorus Jul 8 '15 at 9:07
  • $\begingroup$ @Dorus Well, even calculating 4^3 and 3^4 then! $\endgroup$ – Rand al'Thor Jul 8 '15 at 9:10
  • $\begingroup$ @Bob It's a standard precalc identity: $$\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n=\lim_{n\to\infty}\exp\left\{n{}{\log}\left(1+\frac{1}{n}\right)\right\}$$ $$=\exp\left\{\lim_{n\to\infty}n\log\left(1+\frac{1}{n}\right)\right\}$$ $${}{}=\exp\left\{\lim_{n\to\infty}\frac{\log\left(1+\frac{1}{n}\right)}{n^{-1}}\right\}$$ $$=\exp\left\{\lim_{n\to\infty}\frac{\left(1+\frac{1}{n}\right)^{-1}(-n^{-2})}{-n^{-2}}\right\}$$ $$=\exp\left\{\lim_{n\to\infty}\frac{n}{n+1}\right\}$$ $$=\exp(1)=e$$ $\endgroup$ – 2012rcampion Jul 8 '15 at 13:30
0
$\begingroup$

For sufficiently large $n$, we can check via division and limits.

$$ \frac{n^{(n+1)}}{(n+1)^n} \\ =\frac{n^{(n+1)}}{(n^n+j*n^{n-1}+k*n^{n-2}+...)} \\ =\frac{n^{(n+1)}}{(n^n+j*n^{n-1}+k*n^{n-2}+...)}*\frac{1/n^n}{1/n^n} \\ =\frac{n}{1+j/n+k/n^2+...} \\ \lim_{n\to\infty}\frac{n}{1+j/n+k/n^2+...}=\infty $$

So we can conclude that for sufficiently large $n$, $$n^{(n+1)} > (n+1)^n \\$$

2012rcampion did the work to show the threshold, where $n$ must be greater than 2.

$\endgroup$
  • 1
    $\begingroup$ This proof doesn't work. The value $j$ and $k$ depend on $n$, and the number of summands also grows with $n$. $\endgroup$ – xnor Jul 8 '15 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.