# Hint for prove $\forall n \in \Bbb N \sum _{i=1}^{n} \frac {1}{i!} \le 2 - \frac{1}{2^{n-1}}$?

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.

• you mean $\sum_{i=2}^n \frac{1}{i!}$ ? because $\sum_{i=1}^\infty \frac{1}{i!} = e > 2$ – reuns Apr 25 '16 at 16:41
• 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. – shardulc Apr 25 '16 at 16:42
• @user1952009 In fact $$e=\sum_{i=0}^{\infty}\frac1{i!}$$ – Ángel Mario Gallegos Apr 25 '16 at 16:46
• @ÁngelMarioGallegos : right it explains everything, sorry for my dumb comment – reuns Apr 25 '16 at 16:48

## 2 Answers

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$.

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}