Prove by induction that for all $n \geq 3$: $n^{n+1} > (n+1)^n$

I am currently helping a friend of mine with his preperations for his next exam. A big topic of the exam will be induction, thus I told him he should practice this a lot. As at the beginning he had no idea how induction worked, I showed him some typical examples.

Now he showed me an exercise he was having trouble with, which states that one should prove $$n^{n+1} > (n+1)^n$$ for all $n \geq 3$. I have to admit that I too have trouble showing this inequality, as in all of my attempts, my lower bound is too low. Also, I have not yet figured out, how one gets the $(n+2)^{n+1}$, primarely the number $2$ is a problem. I think this might be solved using the binomial theorem, however, I don't think they have already seen the binomial theorem in school.

Is there an easy method to show this inequality by induction not using the binomial theorem? If no: How can one show it using the binomial theorem?

Thanks for answers in advance.

Solution 1:

Sometimes the trick is to write the problem in a different form.

The inequality is equivalent to

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

The inductive step follows this way:

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

Use P(n) and you are done....

Solution 2:

Suppose that the claim holds for $n$, so we have $$n^{n+1} > (n+1)^n$$

For a proof by contradiction, suppose that the claim fails for $n+1$, so we have: $$(n+2)^{n+1} \geq (n+1)^{n+2}$$

Mulpitlying these two inequalities gives: $$ (n^2 + 2n)^{n+1} = (n(n+2))^{n+1} > (n+1)^{2n+2} = (n^2+2n+1)^{n+1}$$ Clearly, this is impossible. So, the claim for $n+1$ has to hold as well.

Solution 3:

Hint: What about trying to show an equivalent inequality $n>\left(1+\frac1n\right)^n$ for $n\ge 3$ instead?

Spoiler:

$1^\circ$ It holds for $n=3$, since $3>\frac{4^3}{3^3}=\frac{64}{27}=2+\frac{10}{27}$.
$2^\circ$ Assume that it holds for $n$. Then $n+1=n\left(1+\frac1n\right) > \left(1+\frac1n\right)\left(1+\frac1n\right)^n = \left(1+\frac1n\right)^{n+1} > \left(1+\frac1{n+1}\right)^{n+1}$.

Solution 4:

Hint: show $$\frac{(n+1)^{n+2}}{(n+2)^{n+1}}> \frac{n^{n+1}}{(n+1)^n}$$ for $n>3$, or $$(n+2)^{n+1}n^{n+1}<(n+1)^{2n+2}.$$ (This is simply $(n+2)n<(n+1)^2$.)

Solution 5:

Also

$\left ( 1 + \frac{1}{n} \right )^{n} = \sum_{i=0}^{n} \binom{n}{i}\left ( \frac{1}{n} \right )^{i}=2+\sum_{i=2}^{n}\frac{1}{i!}\left ( \frac{1}{n} \right )^{i-1}\cdot (n-1)\cdot (n-2)\cdot ... \cdot (n-i+1)=$ $=2+\sum_{i=2}^{n}\frac{1}{i!}\cdot (1-\frac{1}{n})\cdot (1-\frac{2}{n})\cdot ... \cdot (1-\frac{i-1}{n}) < ...$

(because $0<1-\frac{k}{n} < 1$, when k < n)

$...<2+\sum_{i=2}^{n}\frac{1}{i!}< ...$

(the final piece is $k! > 2^{k-1}$)

$...<2+\sum_{i=2}^{n}\frac{1}{2^{i-1}}=1+\frac{1-\left ( \frac{1}{2} \right )^{n}}{1-\frac{1}{2}}=3-\left ( \frac{1}{2} \right )^{n-1}<3$

As a result $\left ( 1 + \frac{1}{n} \right )^{n} < 3$