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.

  • 1
    You can’t use what you’re trying to prove as your induction hypothesis.2012-12-24
  • 0
    should i take summation part?2012-12-24
  • 0
    Ignore my previous answer: one of the inequalities was backwards.2012-12-24
  • 0
    @Brian, okay no prob.2012-12-24
  • 0
    http://math.stackexchange.com/questions/254335/prove-that-5-2-e-32012-12-24
  • 0
    @Haskell: Please avoid `\displaystyle` in the title. It takes a lot of the front page space. Often too much.2013-03-11
  • 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
    wow, thanks @Haskell2012-12-24
  • 0
    You're most welcome. :)2012-12-24
  • 0
    can you pls expend again your step with "By Cancelation of Terms". i cannot see thru the step.2012-12-24
  • 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.

  • 0
    The binomial coefficient is $\frac{1}{k!}(n)(n-1)\cdots(n-k+1)$. When we multiply by $1/n^{n-k}$, we get $\frac{1}{k!}$ times a bunch of terms that are each $\le 1$.2012-12-24
  • 1
    @doniyor Proving any statement for all natural numbers **will need** to make use of induction (sometimes the induction will be hidden). In case of the proof Andre suggests, the induction is used to prove the binomial theorem in the first place and in the subsequent "algebraic manipulations" you perform.2012-12-24
  • 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