0
$\begingroup$

I am studying computer science in first term, and i got a task that i was not able to solve for a long time now.

I have to prove that

$ 3 > (1+\frac{1}{n})^n>=2$

for every $n \in \mathbb{N}$

$(1+\frac{1}{n})^n>=2$

Can be proved easily with Bernoullis Inequality:

$(1+x)^n>=1+x*n$
$(2= 1+\frac{1}{n}*n)$

Thats cool. But how do i prove that it is smaller than 3? I thought of the following. Using bionomical theorem we can write the above term as:

$$\sum_{k=0}^n\binom{n}{k}*\frac{1}{n^k}$$

If we write the first to sums for k= 0 and k= 1 seperately, we can see that they both equal 1. $$\binom{n}{0}*\frac{1}{n^0}$$ And

$$\binom{n}{1}*\frac{1}{n^1}$$ Both equal one, am i correct.

So the sum $$\sum_{k=2}^N\binom{n}{k}*\frac{1}{n^k}$$ (Without the first two sums) has to be >1. But thats where my problem is. I mean i already proved that Each of the sums is smaller than 1 but that doesnt prove anything, right? $>1+>1\neq >1$ if you know what i mean. The whole thing has to be proofed to be smaller than 1. How can i see that.

P.S: The answer is NOT that the above term wont get bigger as Eulers Number, as by definition. I mean this statement is correct, but it would not solve the question. I really have to, and want, to show it on my own.

Any help is much apprechiated, been thinking about this for so many hours now.

$\endgroup$
0

4 Answers 4

3
$\begingroup$

You can prove the upper bound directly without resorting to the full binomial expansion or the Taylor series.

Let $b_n = \left(1+\frac{1}{n}\right)^{n+1}$. Claim $b_n$ is decreasing. Indeed, \begin{align*} \frac{b_{n+1}}{b_n} &= \left(\frac{1+\frac{1}{n+1}}{1+\frac{1}{n}}\right)^{n+1}\left(1+\frac{1}{n+1}\right) \\ &= \left(\frac{n^2+2n}{n^2+2n+1}\right)^{n+1}\cdot\frac{n+2}{n+1} \\ &= \left(1-\frac{1}{(n+1)^2}\right)^{n+1}\cdot\frac{n+2}{n+1}. \end{align*} Taking the first three terms of the binomial expansion, we see that this is \begin{align*} &\le \left(1-\frac{n+1}{(n+1)^2} + \frac{(n+1)n}{2(n+1)^4}\right)\cdot\frac{n+2}{n+1} \\ &= \frac{2 n^4+8 n^3+11 n^2+6 n}{2n^4 + 8n^3 + 12n^2 + 8n+2} < 1. \end{align*} So $\frac{b_{n+1}}{b_n} < 1$ and thus the $b_n$ are decreasing.

Let $a_n = \left(1+\frac{1}{n}\right)^n$. Clearly $b_n > a_n$. Since $b_6 < 3$, it follows that $b_n<3$ and thus $a_n < 3$ for $n\ge 6$. Checking $a_n$ for $n\le 6$ completes the proof.

$\endgroup$
8
  • $\begingroup$ Yeah, not very pretty. It probably wasn't obvious from my comments, but I know a very nice proof of this using just one well known inequality. I wonder if I should post it as another answer. $\endgroup$ Commented Nov 5, 2014 at 22:22
  • $\begingroup$ ... probably not, as you have to check so many low values :/ $\endgroup$ Commented Nov 5, 2014 at 22:39
  • $\begingroup$ @user2345215 What's the proof? $\endgroup$
    – rogerl
    Commented Nov 5, 2014 at 23:12
  • $\begingroup$ Two questions: 1. Why can you claim bn is decreasing? 2. Don't you have to switch every n for n+1? In the beginning you just set the exponent n+1. $\endgroup$ Commented Nov 6, 2014 at 8:28
  • 1
    $\begingroup$ @FalcoWinkler The two collections of computations below the claim prove it. $\endgroup$
    – rogerl
    Commented Nov 6, 2014 at 13:19
2
$\begingroup$

You already expanded it, so look at the individual terms: $$\binom nk\frac1{n^k}=\frac{n(n{-}1)\ldots(n{-}k{+}1)}{k!}\cdot\frac1{n^k}<\frac{n^k}{k!}\cdot\frac1{n^k}=\frac{1}{k!}$$ Therefore $$\biggl(1+\frac1n\biggr)^n<\sum_{k=0}^n\frac1{k!}<2+\sum_{k=2}^\infty\frac1{k!}<2+\sum_{k=1}^\infty\frac1{2^k}=2+1=3$$

$\endgroup$
2
  • $\begingroup$ You didn't say so, but in passing you did use that the expression is $<e$ ;) $\endgroup$ Commented Nov 5, 2014 at 21:25
  • $\begingroup$ @HagenvonEitzen True :), it's in fact not hard to turn this into the proof that $e=\sum_{k=0}^\infty\frac1{k!}$. I was thinking about some clever use of known inequalities, but it didn't immediately occur to me and I saw already expanded binomials. $\endgroup$ Commented Nov 5, 2014 at 21:29
2
$\begingroup$

$$ (1+\frac{1}{n})^n=\binom{n}{0}1^n\frac{1}{n}^0+\binom{n}{1}1^{n-1}\frac{1}{n}^1+\binom{n}{2}1^{n-2}\frac{1}{n}^2+\binom{n}{3}1^{n-3}\frac{1}{n}^3+...\\=1+n\frac{1}{n}+\frac{n(n-1)}{2}\frac{1}{n^2}+\frac{n(n-1)(n-3)}{3!}\frac{1}{n^3}+...=\\1+1+\frac{n-1}{2n}+\frac{(n-1)(n-2)}{6n^2}+...>1+1=2\overset{n>1}{\rightarrow}\\now\\\\1+1+\frac{n-1}{2n}+\frac{(n-1)(n-2)}{6n^2}+...<1+1+\frac{1}{2}+\frac{1}{6}+\frac{1}{24}+...\\<1+1+(\frac{1}{2})+(\frac{1}{6})+(\frac{1}{12})+...\\<1+1+(\frac{1}{1}-\frac{1}{2})+(\frac{1}{2}-\frac{1}{3})+(\frac{1}{3}-\frac{1}{4})+...<1+1+1=3$$

$\endgroup$
0
$\begingroup$

Hint: note that $$\lim_{n \to \infty}\left(1+\frac{1}{n}\right)^n=e$$

$\endgroup$
8
  • $\begingroup$ How does this help? He needs the inequality for all $n$, not just for some sufficiently high. $\endgroup$ Commented Nov 5, 2014 at 21:27
  • $\begingroup$ I can't use this for the proof. See my P.S Note. Also i agree to user2345215. $\endgroup$ Commented Nov 5, 2014 at 21:30
  • $\begingroup$ @user2345215 note that the sequence is increasing, then for all $n$ this sequence is small that $e$ $\endgroup$ Commented Nov 5, 2014 at 21:33
  • $\begingroup$ @AsdrubalBeltran I know, and $(1+\tfrac1n)^{n+1}$ is decreasing, but that's not easy to prove. $\endgroup$ Commented Nov 5, 2014 at 21:34
  • $\begingroup$ @user2345215 A proof is show that $f'(x)>0$, with $f(x)=\left(1+\frac{1}{x}\right)^x$, and $x\geq1$, then $\left(1+\frac{1}{n}\right)^n$ is increasing. $\endgroup$ Commented Nov 5, 2014 at 21:39

Not the answer you're looking for? Browse other questions tagged .