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

Question

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.

Answer 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....

Answer 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.

Answer 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}$.

Answer 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$.)

Answer 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$

Answer 6

In this answer, it is shown by Bernoulli's Inequality, which is in turn shown by induction at the end of that answer, that $\left(1+\frac1n\right)^n$ is an increasing sequence which is term by term less than $\left(1+\frac1n\right)^{n+1}$, which is a decreasing sequence. This means that for all $n\gt0$, $$ \left(1+\frac1n\right)^n\le\left(1+\frac15\right)^6\lt3 $$ Therefore, for $n\ge3$, we have $$ n\ge3\gt\left(1+\frac1n\right)^n $$ which, upon multiplication by $n^n$, gives the requested inequality for $n\ge3$, $$ n^{n+1}\gt(n+1)^n $$

Answer 7

Assume inequality holds for $k$ $$ k^{k+1} > (k+1)^k \\ k^k k > (k+1)^k \\ \left( \frac {k+1}k\right )^k < k \\ \left( 1 + \frac 1k \right )^k < k $$ Now, one needs to check which side is larger for $$ (k+1)^{k+2}\ ?\ (k+2)^{k+1} \\ (k+1)^{k+1} (k+1)\ ?\ (k+2)^{k+1} \\ k+1 \ ? \ \left( \frac {k+2}{k+1}\right )^{k+1} \\ k+1 \ ? \ \left( 1 + \frac 1{k+1}\right )^{k+1} \\ $$ Consider this chain of inequalities $$ \left(1+\frac 1{k+1} \right)^{k+1} > \left(1+\frac 1k \right)^{k+1} = \left(1+\frac 1k \right)^k \left( 1+ \frac 1k\right) $$ Now, use inequality that assumed to be true $$ \left(1+\frac 1k \right)^k \left( 1+ \frac 1k\right) < k \left( 1+ \frac 1k\right) = k + 1 $$ So, the final inequality is $$ k+1 > \left( 1 + \frac 1{k+1}\right )^{k+1} $$ or alternatively $$ (k+1)^{k+2} > (k+2)^{k+1} $$

Answer 8

Define sequence $f(n)$=$\frac{n^{n+1}}{(n+1)^n}$. The inequality $n^{n+1}>(n+1)^n$ is true for a given $n$ if and only if $f(n)>1$.

The inequality holds for n=3, so we now prove our inductive step. Assume that for a given $k$, $f(k)>1$. We now have to show that $f(k+1)>1$.

We see that $\frac{f(k+1)}{f(k)}$=$\frac{\frac{(k+1)^{k+2}}{(k+2)^{k+1}}}{\frac{k^{k+1}}{(k+1)^k}}$=$\frac{(k+1)^{(k+2)+k}}{k^{k+1}(k+2)^{k+1}}$=$\frac{(k+1)^{2k+2}}{(k^2+2k)^{k+1}}$=$\frac{(k^2+2k+1)^{k+1}}{(k^2+2k)^{k+1}}$>1. Thus, $f(n)$ is an increasing sequence, and so $f(k+1)>1$, thus completing our proof by induction.

Answer 9

For the induction step, we want to prove that $$\frac{(k+1)^{k+2}}{(k+2)^{k+1}}\gt 1,$$ given that $$\frac{k^{k+1}}{(k+1)^{k}}\gt 1.$$ Note that $$ \frac{(k+1)^{k+2}}{(k+2)^{k+1}}=\left(\frac{(k+1)^{k+2}}{(k+2)^{k+1}}\cdot \frac{(k+1)^k}{k^{k+1}}\right)\left(\frac{k^{k+1}}{(k+1)^{k}}\right).$$ So it is enough to prove that $$\frac{(k+1)^{k+2}}{(k+2)^{k+1}}\cdot \frac{(k+1)^k}{k^{k+1}}\gt 1.\tag{$1$}$$ Rewrite the left-hand side of $(1)$ as $$\frac{(k+1)^{2k+2}}{(k+2)^{k+1}k^{k+1}}.\tag{$2$}$$ But the expression $(2)$ is the $(k+1)$-th power of $\dfrac{(k+1)^2}{k(k+2)}$, and $(k+1)^2\gt k(k+2)$.

Answer 10

The premise of the question is incorrect. This is not a problem where integer induction is useful for seeing or proving the truth of the statement.

In one form, the problem is to show that $n^{1/n} > {(n+1)}^{1/{(n+1)}}$. This has the inductive $n \to (n+1)$ pattern, but is better understood as the statement that $f(x) = \frac{\log x}{x}$ is decreasing for all real $x \geq 3$ (where the meaning of $3$ is "anything $\geq e$") which is most apparent by differentiation, $f' = \frac{1- \log x}{x^2}$.

In another form, $n > {(1 + \frac{1}{n})}^{n}$, the problem is essentially a request to prove that $n > e = 2.718... $ for all $n \geq 3$, if you allow the fact that $e_n = {(1 + \frac{1}{n})}^{n}$ is an increasing sequence converging to $\hskip2pt e \hskip2pt$ from below. The fact does not require induction, it is another statement about real $n$ and can be proved most easily by computing $\frac{d}{dn}\log e_n$.

A variant of the second form avoids the need to know an accurate value for $e$, or to mention $e$ at all, by using the decreasing sequence of upper bounds $ E_k = {(1 + \frac{1}{k})}^{k+1}$, and selecting a value of $k$ such that $E_k < 3$ (see the recently posted solution by robjohn with $k=6$). The decrease of $E_k$ is again shown by differentiation of $\log E_k$ with respect to real $k$. In this view the problem is (essentially) asking to prove that $e < 3$, which is not fundamentally an inductive statement about any function of $n$.