0

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.

backslash
  • 131
  • 5

1 Answers1

1

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

Masacroso
  • 30,417
  • 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}$$ – backslash Oct 30 '18 at 04: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)$. – Masacroso Oct 30 '18 at 04:26
  • $G(n+1)=3-\frac1{n+1}=\underbrace{3-\frac1n}_{=,G(n)}+\frac1n-\frac1{n+1}$ – Masacroso Oct 30 '18 at 04: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 – backslash Oct 30 '18 at 04:37
  • Hi @Masacroso thanks for help just one more thing: is there any chance you could show me an example of how you are 'subtracting G(n) to each side of the last inequality' - are you saying do something like $$P(n)+\frac{1}{(n+1)!} - (3-\frac{1}{n}) \leq (3 - \frac{1}{n})+\frac{1}{n}-\frac{1}{(n+1)} - (3 - \frac{1}{n})$$ $$= P(n)+\frac{1}{(n+1)!} - (3-\frac{1}{n}) \leq \frac{1}{n}-\frac{1}{n+1}$$ am curious how the P(n) part gets 'subtracted' as well - am missing that step iny my understanding – backslash Oct 30 '18 at 05:11
  • 1
    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)$ – Masacroso Oct 30 '18 at 06:01