Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

10 Answers 10

up vote 9 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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$

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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