6
$\begingroup$

I am trying to prove this statement for all $ n \geq 1 $ using induction: $ \left( 1 + \frac{1}{n} \right)^{n} \leq \sum_{k=0}^{n} \frac{1}{k!} < 3. $

I said:

  • Base case $ n = 1 $: $ \left( 1 + \frac{1}{1} \right)^{1} \leq \sum_{k=0}^{1} \frac{1}{k!} < 3, $ which is okay.

  • Induction step: Suppose that $ \displaystyle \left( 1 + \frac{1}{n} \right)^{n} \leq \sum_{k=0}^{n} \frac{1}{k!} < 3 $ for a given $ n \in \mathbb{N} $.

    Transition from $ n \to n + 1 $: $ \displaystyle \left( 1 + \frac{1}{n + 1} \right)^{n+1} = \left( 1 + \frac{1}{n + 1} \right)^{n} \left( 1 + \frac{1}{n + 1} \right) = \ldots \text{Help} \ldots < 3. $

I need some guidance for proof-writing (-thinking) in orders.

  • 0
    See the accepted answer in [here](http://math.stackexchange.com/questions/200141/calculus-limit-inequality/200153#200153).2013-03-12

4 Answers 4

10

For all $ n \in \mathbb{N} $, we have \begin{align} \left( 1 + \frac{1}{n} \right)^{n} &= \sum_{k=0}^{n} \binom{n}{k} \left( \frac{1}{n} \right)^{k} \quad (\text{By the Binomial Theorem.}) \\ &= \sum_{k=0}^{n} \frac{n!}{k!(n - k)!} \cdot \frac{1}{n^{k}} \quad (\text{By the definition of the binomial coefficient.}) \\ &= \sum_{k=0}^{n} \frac{1}{k!} \cdot \frac{n!}{(n - k)!} \cdot \frac{1}{n^{k}} \\ &= \sum_{k=0}^{n} \frac{1}{k!} \left( \prod_{i=n-k+1}^{n} i \right) \frac{1}{n^{k}} \quad (\text{By cancellation of terms.}) \\ &\leq \sum_{k=0}^{n} \frac{1}{k!} \left( \prod_{i=n-k+1}^{n} n \right) \frac{1}{n^{k}} \quad (\text{As $ i \leq n $ for all $ i \in \{ n - k + 1,\ldots,n \} $.}) \\ &= \sum_{k=0}^{n} \frac{1}{k!} \cdot n^{k} \cdot \frac{1}{n^{k}} \\ &= \sum_{k=0}^{n} \frac{1}{k!} \\ &\leq 1 + \sum_{k=0}^{n-1} \frac{1}{2^{k}} \quad (\text{By comparison of terms.}) \\ &< 1 + \sum_{k=0}^{\infty} \frac{1}{2^{k}} \\ &= 1 + 2 \quad (\text{Sum of a well-known convergent geometric series.}) \\ &= 3. \quad (\text{Voilà!}) \end{align}

  • 0
    Observe that $ n! = 1 \times \cdots \times n $ and $ (n - k)! = 1 \times \cdots \times (n - k) $. Hence, $ \dfrac{n!}{(n - k)!} = (n - k + 1) \times \cdots \times n $ by cancellation.2012-12-24
2

Hint: There is no real need for induction. Use the Binomial Theorem.

  • 3
    @Marvis: Certainly induction is involved in any expression that has $\dots$ (\dots) in it. It all depends on how formal we want the argument to be.2012-12-24
1

Your induction hypothesis $(1+\frac{1}{n})^n\leq\sum_{k=0}^{n}\frac{1}{k!}\lt 3$ for a given $n$, not for all $n$.
In the induction step, since $1+\frac1{n+1}>0$, you can multiply both sides of the i.p. by $1+\frac1{n+1}$, to get $\left(1+\frac{1}{n+1}\right)^{n+1}\leq\left(1+\frac{1}{n}\right)^{n}\left(1+\frac{1}{n+1}\right)\overset{\mbox{i.p.}}{\leq}\left(\sum_{k=0}^{n}\frac{1}{k!}\right)\left(1+\frac{1}{n}\right)=\sum_{k=0}^{n}\frac{1}{k!}+\frac1{n+1}\sum_{k=0}^{n}\frac{1}{k!}$ Can you continue?

1

To show that $\displaystyle\sum_{k=0}^{k=n}\frac{1}{k!} \lt 3$

$\displaystyle\sum_{k=0}^{k=n}\frac{1}{k!}=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\dots+\frac{1}{n!}$

$\displaystyle\sum_{k=0}^{k=n}\frac{1}{k!}=1+1+\frac{1}{2!}+\frac{1}{3!}+\dots +\frac{1}{n!}$

$\displaystyle\sum_{k=0}^{k=n}\frac{1}{k!}=1+1+\frac{1}{2}+\frac{1}{2}\left(\frac{1}{3}+\frac{1}{3*4}+\frac{1}{3*4*5}+\dots+\frac{1}{3*4*5*\dots*n}\right)$

$\displaystyle\sum_{k=0}^{k=n}\frac{1}{k!}\lt1+1+1$

  • 0
    great, nicely done2012-12-24