# Math Induction Proof: $(1+\frac1n)^n < n$

So I have to prove:

For each natural number greater than or equal to 3, $$(1+\frac1n)^n<n$$

My work: Basis step: $n=3$ $$\left(1+\frac13\right)^3<3$$ $$\left(\frac43\right)^3<3$$ $$\left(\frac{64}{27}\right)<3$$ which is true.

Now the inductive step, assume $P(k)=\left(1+\frac1k\right)^k<k$ to be true and prove $P(k+1)=\left(1+\frac1{k+1}\right)^{k+1}<k+1$.

This is where I am stuck because usually you add or multiply by $k+1$ or some similar term.

• Are you sure you're not supposed to show $$\left(1 + \frac1n\right)^n < 3\,?$$ – Daniel Fischer Nov 26 '13 at 21:30
• @DanielFischer, that would be harder. – dfeuer Nov 26 '13 at 22:03
• @dfeuer For sure. But it would not be an exceptional exercise. – Daniel Fischer Nov 26 '13 at 22:05
• Is it possible to prove something with limits? Because $\left( 1\; +\; \frac{1}{n} \right)^{n}$ tends to $e$ as $n$ approaches infinity...? – 1110101001 Nov 29 '13 at 0:27

Hint: $$\left( 1+\frac{1}{k+1} \right)^{k+1} = \left( 1 + \frac{1}{k+1}\right) \left( 1 + \frac{1}{k+1}\right)^{k} < \left( 1 + \frac{1}{k+1}\right) \left( 1 + \frac{1}{k}\right)^{k}\\ < \left( 1 + \frac{1}{k+1}\right)k$$ where the last inequality comes from your induction hypothesis.

• Alright I understand how you broke down the $$\left(1+\frac1{k+1}\right)^{k+1}=\left(1+\frac1{k+1}\right)\left(1+\frac1{k+1}\right)^k$$ but I do not see how you got the inequality from the hypothesis – user111702 Nov 26 '13 at 21:42
• The first inequality is simply because $\frac{1}{k+1} < \frac{1}{k}$. The second inequality was by the induction hypothesis that $$\left( 1 + \frac{1}{k} \right)^k < k$$ – Tom Nov 26 '13 at 21:44
• So from the hypothesis you multiply both sides by a factor of $$\left(1+\frac1{k+1}\right)$$ and get $$\left(1+\frac1{k+1}\right)\left(1+\frac1k\right)^k<\left(1+\frac1{k+1}\right)k$$ right? – user111702 Nov 26 '13 at 21:50
• That's one way to see it. I just considered the following $$\left( 1+\frac{1}{k+1} \right) \underbrace{ \left(1+\frac{1}{k} \right)^k }_{<k \text{ by hypothesis}} < \left(1 + \frac{1}{k+1} \right)k$$ – Tom Nov 26 '13 at 21:51
• Alright so then how do you know that $$\left(1+\frac1{k+1}\right)\left(1+\frac1{k+1}\right)^k<\left(1+\frac1{k+1}\right)\left(1+\frac1{k}\right)^k$$ – user111702 Nov 26 '13 at 21:56

$\left(1+\frac 1 n\right)^n=1+1+\binom n 2\frac 1 {n^2}+\binom n 3 \frac 1 {n^3}+\dotsb+\frac 1 {n^n}$

But $\binom n k \frac 1 {n^k}=\frac {n(n-1)\dotsm(n-k+1)}{k!n^k}<\frac 1 {k!}$.

So the expression we're interested in is less than $$1+1+\frac 1 {2!}+\frac 1{3!}+\dotsb+\frac 1 {n!}<1+1+\frac 1 2 +\frac 1 4 +\frac 1 8+\dotsb=3.$$

This is equivalent to proving $$P(n)\colon\qquad (n+1)^n <n^{n+1}$$ for $n\ge3$.

Inductive step: We assume that $P(k-1)$ holds, i.e., that $$k^{k-1}<(k-1)^k.$$ We will prove $P(k)$ by contradiction.

Assume that $P(k)$ does not hold, i.e., $$(k+1)^k \ge k^{k+1}.$$

By multiplying the inequalities \begin{align*} (k-1)^k &> k^{k-1}\\ (k+1)^k &\ge k^{k+1} \end{align*} we get $$(k^2-1)^k \ge k^{2k},$$ i.e., $(k^2-1)^k \ge (k^2)^k$, which is a contradiction.

This can be used to show that the sequence $\sqrt[n]{n}$ is eventually decreasing. I guess there are a few posts about this question, but I was not able to find some such post quickly.