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

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?

• For this problem, use $\left(1+\frac{1}{n+1}\right) < \left(1+\frac{1}{n}\right)$ to get the conclusion. Feb 9, 2014 at 9:41
• wait what... but that means that I have to take $P(n+1) < P(n)$ which is $\left(1+\frac{1}{n+1}\right) < \left(1+\frac{1}{n}\right)$, but what do I do next? Feb 9, 2014 at 9:42
• Remember to keep clearly separate in your mind the inequalities you have assumed or derived from the inequalities you're trying to obtain. Feb 9, 2014 at 9:43
• If I'm just plugging any number for $n$ I'll be able to see it, but I can't do that because that's not how a proof works. Feb 9, 2014 at 9:45
• In fact the much stronger bound $(1+\frac{1}{n})^n < 3$ holds for all $n$. So for $n ≥ 3$ this includes your inequality. But of course it takes a little more effort to prove.
– bodo
Feb 9, 2014 at 9:59

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

• I should've used that earlier! Using the Binomial Theorem makes this problem a whole lot easier. Feb 9, 2014 at 22:37
• Sure, but make sure you understand induction too! Otherwise I'll feel bad for doing you homework for you. Besides, induction is one of the most important ideas in mathematics. Feb 9, 2014 at 22:47
• I have been practicing induction problems like the ones I listed above which is $1+2+3+...+n = n+2$ and $7^n-8^n$ is divisible by $8$. This problem was a bit confusing because I did the basis and the equations holds true. I did $P(n)$ and that was easy, but the $P(n+1)$ part was very frustrating. I'm reading more about how to do the $P(n+1)$ because I want to learn how the whole process really works. I know there are a ton of different problems that use induction and not all of the steps are the same. I can't apply whatever I did earlier to this. Feb 9, 2014 at 23:16
• ...and that sucks because there is induction for geometric series ... induction for ... I don't what it's called but there was a fraction like this $\frac{1}{2*3} + \frac{1}{3*4}$ Feb 9, 2014 at 23:18

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?

• ok wait... ummmm so we have $\left(1+\frac{1}{n+1}\right) < \left(1+\frac{1}{n}\right)$ and that was spliced into this $\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$ ..............so my question is that well did we factor out something to have it lead to the $(1 + \frac{1}{n+1})^n < (1+\frac{1}{n})^n$ ? Feb 9, 2014 at 9:58
• @usukidoll Are you asking how to get from $\left(1+\frac{1}{n+1}\right) < \left(1+\frac{1}{n}\right)$ to $\left(1+\frac{1}{n+1}\right)^n < \left(1+\frac{1}{n}\right)^n$? You raise each side to the $n$-th power. Feb 9, 2014 at 10:05
• no. I'm asking for$\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.$ The top one with the $< \leftrightarrow <$ part. Feb 9, 2014 at 10:07
• @usukidoll: we add +1 on both sides there.
– bodo
Feb 9, 2014 at 10:13
• @usukidoll Take the inequality $\frac{1}{n+1}<\frac{1}{n}$ and add $1$ to each side. Feb 9, 2014 at 10:14

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.

• This is not very helpful as a general approach as you don’t always get the assumption as a factor. You need to write down the induction hypothesis and look where you can apply the assumption.
– bodo
Feb 9, 2014 at 10:08
• Woops, similar to David H's response but hope it helps, let me know if you want help with the algebra :) Feb 9, 2014 at 10:08
• I find that this actually works quite well for many inequality induction problems. Feb 9, 2014 at 10:09
• really? isn't that similar to the $1+2+3+...+n = n+2$ problem when after we do $P(n+1)$ we need to work on the left to achieve the right? Maybe algebra for the left side would work to get to the right side which is $(\frac{k+1}{k})$ Feb 9, 2014 at 10:11
• Just be careful that your formulas don’t get unnecessary complicated.
– bodo
Feb 9, 2014 at 10:12

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.

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?

• not really...sorry I'm kind of slow at this. And since there are so many induction problems out there, each one has a unique technique to tackle them Feb 9, 2014 at 9:43
• Given that your comment appeared less than one minute after my answer, I don't think slow has anything to do with it. Take some time to ponder it some more - that's where the learning comes from. (And it's not the technique that's different from problem to problem, just the specific ways of relating what you get to assume to what you want to prove.) Feb 9, 2014 at 9:45
• This is my first pure math analysis course. Of course I'll be slower than usual...I'm so used to computation only . So I have to replace something and...? Feb 9, 2014 at 9:46