0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$$ $\endgroup$ – backslash Oct 30 '18 at 4:20
  • $\begingroup$ 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)$. $\endgroup$ – Masacroso Oct 30 '18 at 4:26
  • $\begingroup$ $G(n+1)=3-\frac1{n+1}=\underbrace{3-\frac1n}_{=\,G(n)}+\frac1n-\frac1{n+1}$ $\endgroup$ – Masacroso Oct 30 '18 at 4:28
  • $\begingroup$ 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 $\endgroup$ – backslash Oct 30 '18 at 4:37
  • 1
    $\begingroup$ 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)$ $\endgroup$ – Masacroso Oct 30 '18 at 6:01

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.