8
$\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$
4
  • 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, 2015 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$ Jul 8, 2015 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$ Jul 8, 2015 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, 2015 at 12:57

4 Answers 4

16
$\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$
4
  • $\begingroup$ Very good. This is what I was looking for! $\endgroup$ Jul 8, 2015 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, 2015 at 13:58
  • 1
    $\begingroup$ @Nyk232 You divide by $n^n$ on both sides. $\endgroup$
    – mmking
    Jul 8, 2015 at 14:14
  • $\begingroup$ @mmking ahh, I see now. thanks for letting me know! $\endgroup$
    – Nyk 232
    Jul 8, 2015 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$
4
  • 6
    $\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$ Jul 8, 2015 at 3:12
  • $\begingroup$ @2012rcampion very good points! $\endgroup$ Jul 8, 2015 at 3:14
  • $\begingroup$ Another interesting approach, +1 $\endgroup$ Jul 8, 2015 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, 2015 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$
4
  • $\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$ Jul 8, 2015 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, 2015 at 9:07
  • $\begingroup$ @Dorus Well, even calculating 4^3 and 3^4 then! $\endgroup$ Jul 8, 2015 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$ Jul 8, 2015 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
  • 2
    $\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, 2015 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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