2
$\begingroup$

I'm trying to prove the following inequality $\forall n \in \Bbb N$: $$\sum _{i=1}^{n} \frac {1}{i!} \le 2 - \frac{1}{2^{n-1}}$$

I'm doing it by induction. It's true for $P(1)$.

So now I want to prove it for $P(n+1)$.

$$\sum _{i=1}^{n+1} \frac {1}{i!} \le 2 - \frac{1}{2^{n}}$$

I assume the inductive hypothesis for $P(n)$: $\sum _{i=1}^{n} \frac {1}{i!} \le 2 - \frac{1}{2^{n-1}}$ I'm left with:

$$\sum _{i=1}^{n} \frac {1}{i!} + \frac{1}{(n+1)!} \le 2 - \frac{1}{2^{n}}$$

I'm not assure what step to take next, I should bound it somehow but it's not clear to me how. If anyone could suggest me the next move... thanks.

$\endgroup$
  • 1
    $\begingroup$ you mean $\sum_{i=2}^n \frac{1}{i!}$ ? because $\sum_{i=1}^\infty \frac{1}{i!} = e > 2$ $\endgroup$ – reuns Apr 25 '16 at 16:41
  • $\begingroup$ You are adding something to the left-hand side and something to the right-hand side. If the left something is less than the right something, and the initial case is true, then you are done. $\endgroup$ – shardulc Apr 25 '16 at 16:42
  • 1
    $\begingroup$ @user1952009 In fact $$e=\sum_{i=0}^{\infty}\frac1{i!}$$ $\endgroup$ – Ángel Mario Gallegos Apr 25 '16 at 16:46
  • $\begingroup$ @ÁngelMarioGallegos : right it explains everything, sorry for my dumb comment $\endgroup$ – reuns Apr 25 '16 at 16:48
1
$\begingroup$

Hint:

It will be sufficient to show that $$\frac{1}{(n+1)!}\le\frac{1}{2^{n-1}}-\frac{1}{2^n}=\frac{1}{2^n}$$ which follows easily from the fact $$2^n\le (n+1)!\qquad n\ge 1\text{ integer}\tag{1}$$ Inequality $(1)$ holds since $2\le 1\cdot 2$ and $2< i+1$ for all $1<i\le n$.

$\endgroup$
1
$\begingroup$

As Angel's answer notes, an ancillary inequality will be of use here, namely $$ 2^n\leq(n+1)!,\qquad n\geq1\tag{1} $$ which may be easily proved as well using induction (here is the meat of the inductive proof for $(1)$): $$ 2^{k+1}=2^k\cdot2\leq(k+1)!\cdot2\leq(k+1)!\cdot(k+2)=(k+2)!. $$ Hence, $$ 2^n\leq(n+1)!\Longleftrightarrow\frac{1}{2^n}\geq\frac{1}{(n+1)!}.\tag{2} $$ Thus, the inductive step of your argument looks like so: \begin{align} \sum_{i=1}^{k+1}\frac{1}{i!}&= \sum_{i=1}^k\frac{1}{i!}+\frac{1}{(k+1)!}\tag{by definition}\\[1em] &\leq 2-\frac{1}{2^{k-1}}+\frac{1}{(k+1)!}\tag{by inductive hypothesis}\\[1em] &\leq 2-\frac{1}{2^{k-1}}+\frac{1}{2^k}\tag{by $(2)$}\\[1em] &= 2-\frac{2}{2^k}+\frac{1}{2^k}\tag{rewrite}\\[1em] &= 2-\frac{1}{2^k}.\tag{simplify} \end{align}

$\endgroup$

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.