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.
 A: 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$.)
A: 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....
A: 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$
A: 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
$$
A: 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.
A: 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}$.

A: 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)$.  
A: 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.
A: 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}
$$
A: 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$.
