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.

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

  • $\begingroup$ 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 $\endgroup$ – user111702 Nov 26 '13 at 21:42
  • $\begingroup$ 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$$ $\endgroup$ – Tom Nov 26 '13 at 21:44
  • $\begingroup$ 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? $\endgroup$ – user111702 Nov 26 '13 at 21:50
  • $\begingroup$ 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$$ $\endgroup$ – Tom Nov 26 '13 at 21:51
  • $\begingroup$ 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$$ $\endgroup$ – 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.


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.