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?

  • $\begingroup$ For this problem, use $\left(1+\frac{1}{n+1}\right) < \left(1+\frac{1}{n}\right)$ to get the conclusion. $\endgroup$ – Daniel Fischer Feb 9 '14 at 9:41
  • $\begingroup$ 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? $\endgroup$ – usukidoll Feb 9 '14 at 9:42
  • $\begingroup$ Remember to keep clearly separate in your mind the inequalities you have assumed or derived from the inequalities you're trying to obtain. $\endgroup$ – Greg Martin Feb 9 '14 at 9:43
  • $\begingroup$ 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. $\endgroup$ – usukidoll Feb 9 '14 at 9:45
  • 1
    $\begingroup$ 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. $\endgroup$ – bodo Feb 9 '14 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*}$$

| cite | improve this answer | |
  • $\begingroup$ I should've used that earlier! Using the Binomial Theorem makes this problem a whole lot easier. $\endgroup$ – usukidoll Feb 9 '14 at 22:37
  • $\begingroup$ 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. $\endgroup$ – Oscar Cunningham Feb 9 '14 at 22:47
  • $\begingroup$ 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. $\endgroup$ – usukidoll Feb 9 '14 at 23:16
  • $\begingroup$ ...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}$ $\endgroup$ – usukidoll Feb 9 '14 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?

| cite | improve this answer | |
  • $\begingroup$ 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$ ? $\endgroup$ – usukidoll Feb 9 '14 at 9:58
  • $\begingroup$ @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. $\endgroup$ – David H Feb 9 '14 at 10:05
  • $\begingroup$ 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. $\endgroup$ – usukidoll Feb 9 '14 at 10:07
  • $\begingroup$ @usukidoll: we add +1 on both sides there. $\endgroup$ – bodo Feb 9 '14 at 10:13
  • $\begingroup$ @usukidoll Take the inequality $\frac{1}{n+1}<\frac{1}{n}$ and add $1$ to each side. $\endgroup$ – David H Feb 9 '14 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – bodo Feb 9 '14 at 10:08
  • $\begingroup$ Woops, similar to David H's response but hope it helps, let me know if you want help with the algebra :) $\endgroup$ – liedora Feb 9 '14 at 10:08
  • $\begingroup$ I find that this actually works quite well for many inequality induction problems. $\endgroup$ – liedora Feb 9 '14 at 10:09
  • $\begingroup$ 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})$ $\endgroup$ – usukidoll Feb 9 '14 at 10:11
  • $\begingroup$ Just be careful that your formulas don’t get unnecessary complicated. $\endgroup$ – bodo Feb 9 '14 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.

| cite | improve this answer | |

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?

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – usukidoll Feb 9 '14 at 9:43
  • 1
    $\begingroup$ 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.) $\endgroup$ – Greg Martin Feb 9 '14 at 9:45
  • $\begingroup$ 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...? $\endgroup$ – usukidoll Feb 9 '14 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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