Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
You can’t use what you’re trying to prove as your induction hypothesis. –  Brian M. Scott Dec 24 '12 at 7:42
    
should i take summation part? –  doniyor Dec 24 '12 at 7:44
    
Ignore my previous answer: one of the inequalities was backwards. –  Brian M. Scott Dec 24 '12 at 7:55
    
@Brian, okay no prob. –  doniyor Dec 24 '12 at 7:57
    
show 2 more comments

4 Answers

up vote 9 down vote accepted

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}

share|improve this answer
    
wow, thanks @Haskell –  doniyor Dec 24 '12 at 8:26
    
You're most welcome. :) –  Haskell Curry Dec 24 '12 at 8:33
    
can you pls expend again your step with "By Cancelation of Terms". i cannot see thru the step. –  doniyor Dec 24 '12 at 9:25
    
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. –  Haskell Curry Dec 24 '12 at 15:06
add comment

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

share|improve this answer
    
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$. –  André Nicolas Dec 24 '12 at 7:54
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. –  user17762 Dec 24 '12 at 7:55
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. –  André Nicolas Dec 24 '12 at 7:57
add comment

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?

share|improve this answer
add comment

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$

share|improve this answer
    
great, nicely done –  doniyor Dec 24 '12 at 9:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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