# Proof by Induction involving Inequality and Factorials as denominators

Have had a lot of trouble with this question. Cannot seem to use the components from the induction hypothesis properly.

Prove by induction:

P(n): $$1+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{n!} \leq 3 - \frac{1}{n}$$ for all $$n \in \Bbb N$$

So i'm able to prove the base case:

P(1): $$1+\frac{1}{(1)!} \leq 3 - \frac{1}{1} = 2 \leq 2$$ is true.

Induction: Assume that

P(k): $$1+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{k!} \leq 3 - \frac{1}{k}$$ is true for some $$k \in \mathbb N$$

Have to show that

P(k+1): $$1+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{k!}+\frac{1}{(k+1)!} \leq 3 - \frac{1}{(k+1)}$$

So I get up to this step but don't know how to proceed after it: $$1+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{k!}+\frac{1}{(k+1)!} \leq 3 - \frac{1}{k}+\frac{1}{(k+1)!}$$

(using the $$3-\frac{1}{k}$$ from the induction hypothesis (P(k)) but I have no idea how to start working with with these factorials to arrive at a conclusion that matches the RHS of P(k+1). I'm thinking there's something to do with that $$(k+1)! = (k+1)k!$$ but can't connect it all.

Any help would be appreciated - I checked everywhere on here and closest question I found that was similar was this question but it involves equality vs inequality. Thanks hopefully can help. I think this is question is unique enough that it shouldn't be a duplicate.

HINT: let $$P(n):=\sum_{k=0}^n\frac1{k!}$$ and $$G(n):=3-\frac1n$$, and we assume by hypothesis that $$P(n)\le G(n)$$, then you want to show that
$$P(n+1)=P(n)+\frac1{(n+1)!}\le G(n+1)=G(n)-\frac1{n+1}+\frac1n$$
so it is enough to show that $$\frac1{(n+1)!}\le\frac1n-\frac1{n+1}$$ for all $$n\in\Bbb N_{\ge 1}$$.
• Okay so I follow how you're saying how $$G(n): 3-\frac{1}{n}$$ and how you've arrange $$P(n+1) = P(n) + \frac{1}{(n+1)!} \leq G(n+1)$$ $$G(n+1) = G(n)-\frac{1}{(n+1)}+\frac{1}{n}$$ - i'm just having trouble why you add the $$\frac{1}{n}$$ to $$3- \frac{1}{n}$$ (G(n)) and how do you get to the bottom part where you show that $$\frac{1}{(n+1)!} \leq \frac{1}{n}-\frac{1}{n+1}$$ Oct 30 '18 at 4:20
• note that $P(n)\le G(n)\Leftrightarrow P(n)-G(n)\le 0$, and you have that $G(n+1)=G(n)-\frac1{n+1}+\frac1n$ (check it using the definition of $G$). Also we have that $P(n+1)=P(n)+\frac1{(n+1)!}$, so $P(n+1)\le G(n+1)$ is the same that $$P(n)+\frac1{(n+1)!}\le G(n)+\frac1n-\frac1{n+1}$$ Now subtracting $G(n)$ to each side of this last inequality we find that it is enough to show that $\frac1{(n+1)!}\le\frac1n-\frac1{(n+1)}$ to prove that $P(n+1)\le G(n+1)$. Oct 30 '18 at 4:26
• $G(n+1)=3-\frac1{n+1}=\underbrace{3-\frac1n}_{=\,G(n)}+\frac1n-\frac1{n+1}$ Oct 30 '18 at 4:28
• ohhhhhh okay thanks pretty sure i'm seeing what i'm missing - (now obvious) fact that $P(n) \leq G(n) \Leftrightarrow P(n) - G(n) \leq 0$ and your last comment helping a lot Oct 30 '18 at 4:37
• Note that $P(n)-G(n)\le 0$ by assumption (by the induction hypothesis) so if we shows that $\frac1{(n+1)!}\le \frac1n-\frac1{n+1}$ it would be also true that $P(n)-G(n)+\frac1{(n+1)!}\le \frac1n-\frac1{n+1}$, what is equivalent to say that $P(n+1)\le G(n+1)$ Oct 30 '18 at 6:01