Prove that the inequality $(1+ \frac{1}{n})^n < n$ holds for all $n \geq 3$

Question

First we need to prove the basis. If we let $n=3$, then $(1+ \frac{1}{3})^3 < 3$

$(\frac{3}{3}+ \frac{1}{3})^3 < 3$

$(\frac{4}{3})^3 < 3$

$(\frac{64}{27}) < 3$

The inequality statement is true

For $P(n), (1+ \frac{1}{n})^n < n$

We assume that $(1+ \frac{1}{n})^n < n$ is true for $P(n+1)$

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

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

And then I'm stuck afterwards. I know that there are a variety of problems that use induction and they have different methods, but I only know the ones that are similar to $1+2+3+...+n = n+2$ or $7^n-8^n$ is divisible by $8$. Is there any technique to tackle this type of problem?

Answer 1

As canaaerus points out in the comments, we can in fact prove $$\left(1+\frac{1}{n}\right)^n<3$$ In fact there's a proof of this that doesn't even use induction! I think it's worth writing down here since it's so simple (and it won't be giving away the answer to the homework problem, since the teacher presumably expects induction). We will binomially expand and use the following facts: $${{n}\choose{r}}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-r+1)}{r!}\leq\frac{n\cdot n\cdot\ldots\cdot n}{r!}=\frac{n^r}{r!}$$ and (for $r\geq1$) $$\frac{1}{r!}=\frac{1}{1\cdot2\cdot3\cdot4\cdot\ldots\cdot r}\leq\frac{1}{1\cdot2\cdot2\cdot2\cdot\ldots\cdot 2}=\frac{1}{2^{r-1}}$$ Here's the proof: $$\begin{align*} \left(1+\frac{1}{n}\right)^n&=\sum^{n}_{r=0}{{n}\choose{r}}\frac{1}{n^r}\\ &\leq\sum^{n}_{r=0}\frac{n^r}{r!}\frac{1}{n^r}\\ &=\sum^{n}_{r=0}\frac{1}{r!}\\ &=1+\sum^{n}_{r=1}\frac{1}{r!}\\ &\leq1+\sum^{n}_{r=1}\frac{1}{2^{r-1}}\\ &<1+\sum^{\infty}_{r=1}\frac{1}{2^{r-1}}\\ &=1+2=3 \end{align*}$$

Answer 2

The following inequality will be needed: $$\frac{1}{n+1}<\frac{1}{n} \Leftrightarrow 1+\frac{1}{n+1}<1+\frac{1}{n}\\ \Leftrightarrow \left(1+\frac{1}{n+1}\right)^n<\left(1+\frac{1}{n}\right)^n.$$

From the induction hypothesis $\left(1+\frac{1}{n}\right)^n<n$ and the algebraic identity $\left(1+ \frac{1}{n+1}\right)^{n+1} = \left(1+ \frac{1}{n+1}\right)^n\left(1+ \frac{1}{n+1}\right)$,

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

Can you take it from there?

Answer 3

This is the same as $n > (\frac{n+1}{n})^n $ or $\frac{(n+1)^n}{n^{n+1}} < 1 $.

This is true for $n=3$, since $4^3 = 64$ and $3^4 = 81$.

I will show that $\frac{(n+1)^n}{n^{n+1}} $ is decreasing; since this is less than one for $n=3$, this will show that it is less than one for all $n \ge 3$.

Showing this is decreasing is the same as showing that $\frac{(n+1)^n}{n^{n+1}} > \frac{(n+2)^{n+1}}{(n+1)^{n+2}} $. Cross-multiplying, this is the same as $(n+1)^{2n+2} >(n(n+2))^{n+1} $ or $(n^2+2n+1)^{n+1} > (n^2+2n)^{n+1} $ which is obviously true.

Answer 4

This is the technique that I would use...

Induction Step: We assume $$ \left ( 1 + \frac{1}{k} \right ) ^ k < k. $$

Multiplying both sides by "${\color{red}{something}}$" to get our desired outcome gives,

$$ \left ( 1 + \frac{1}{k} \right ) ^ k {\color{red}{\frac{\left( 1 + \frac{1}{k+1} \right )^{k+1}}{\left ( 1 + \frac{1}{k} \right ) ^ k}}} < k{\color{red}{\left(\frac{k+1}{k}\right)}}. $$

So all you need to show (for this inequality to hold) is

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

Which is simple enough with some algebra.

Answer 5

Your approach is totally right. Look for a way to relate what you have at the end to the induction hypothesis. For example, it's certainly true that $$ \bigg( 1 + \frac1{n+1} \bigg)^n < \bigg( 1 + \frac1{n} \bigg)^n. $$ So if you replace the former by the latter in your last desired inequality, does that help you?