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.

$\endgroup$
10
$\begingroup$

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}

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

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Dec 24 '12 at 7:54
  • 1
    $\begingroup$ @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. $\endgroup$ – user17762 Dec 24 '12 at 7:55
  • 3
    $\begingroup$ @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. $\endgroup$ – André Nicolas Dec 24 '12 at 7:57
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ great, nicely done $\endgroup$ – doniyor Dec 24 '12 at 9:40

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.