3
$\begingroup$

Prove if $n \in \mathbb N$, then $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{\left(n+1\right)!} = 1-\frac{1}{\left(n+1\right)!}$

So I proved the base case where $n=1$ and got $\frac{1}{2}$

Then since $n=k$ implies $n=k+1$ I setup the problem like so:

$\frac{k}{(k+1)!}+\frac{(k+1)}{(k+2)!}=1-\frac{1}{(k+2)!}$

After trying to simplify it I got the following:

$\frac{k(k+2)!+(k+1)(k+1)!}{(k+1)!(k+2)!}=1-\frac{1}{(k+2)!}$

However, I'm having trouble simplifying it to match the RHS. Hints?

$\endgroup$
0

4 Answers 4

Reset to default
5
$\begingroup$

I thought it might be instructive to present an approach that is not a proof by induction. To that end, note that we can write

$$\bbox[5px,border:2px solid #C0A000]{\frac{k}{(k+1)!}=\frac{1}{k!}-\frac{1}{(k+1)!}}$$

Therefore, we have a telescoping sum such that

$$\begin{align} \sum_{k=1}^n \frac{k}{(k+1)!}&=\sum_{k=1}^n\left(\frac{1}{k!}-\frac{1}{(k+1)!}\right)\\\\ &=1-\frac{1}{(n+1)!} \end{align}$$

And we are done!

$\endgroup$
2
  • 1
    $\begingroup$ I think that technically telescoping sums are proofs by induction. The mass cancellation of terms is often written using an ellipsis $\cdots$ of one form or another. And that really should be justified by an induction. I joke with my students that using ellipsis is my shorthand for a trivial induction. See my comments under Taha Akbari's answer as well. I do admit that there is scope for different points of view here :-) $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 10, 2016 at 9:23
  • 1
    $\begingroup$ @jyrkilahtonen Jyrki, I agree with you. In particular, your joking with your students about the trivial nature of the induction is spot on. And this was the thinking here. Many students have seen a general telescoping series proof using induction. So, once we are equipped with that tool, we can quicky conclude the closed form of this sum, inasmuch as it can be written as a telescoping one. -Mark $\endgroup$
    – Mark Viola
    Commented Jul 10, 2016 at 20:41
4
$\begingroup$

The equality you want to prove is $$ \underbrace{\frac{1}{2!}+\dots+\frac{k}{(k+1)!}}_{*}+ \frac{k+1}{(k+2)!}=1-\frac{1}{(k+2)!} $$ The term marked $*$ is equal, by the induction hypothesis, to $$ 1-\frac{1}{(k+1)!} $$ and so you need to manipulate $$ 1-\frac{1}{(k+1)!}+\frac{k+1}{(k+2)!} $$ Hint: $$ 1-\frac{1}{(k+1)!}+\frac{k+1}{(k+2)!} = 1-\frac{k+2}{(k+2)!}+\frac{k+1}{(k+2)!} =\dots $$ Do the necessary steps in order to finish up at $1-\dfrac{k+1}{(k+2)!}$.

$\endgroup$
5
  • $\begingroup$ On the hint that you provided, how did you come up with that using the given information? $\endgroup$
    – nullByteMe
    Commented Jun 11, 2016 at 13:46
  • $\begingroup$ @free_mind I just substituted the $*$ part with the expression provided by the induction hypothesis. $\endgroup$
    – egreg
    Commented Jun 11, 2016 at 13:49
  • $\begingroup$ Oh I meant for the RHS? It seems like you added an additional term? Is this because you added the $k+1$ term to each side? $\endgroup$
    – nullByteMe
    Commented Jun 11, 2016 at 13:56
  • $\begingroup$ @free_mind The final equation is the start of the manipulation you should do in order to finish with $1-\dfrac{k+1}{(k+2)!}$. I added some words about it. $\endgroup$
    – egreg
    Commented Jun 11, 2016 at 14:01
  • $\begingroup$ Thanks so much for your time and help. I understand it now! $\endgroup$
    – nullByteMe
    Commented Jun 11, 2016 at 16:34
3
$\begingroup$

You have your base case.

Explicitly state your inductive hypothesis.

Suppose: $\sum_\limits{n=1}^k\frac{n}{(n+1)!} = 1-\frac{1}{(k+1)!}$

We will show that:

$\sum_\limits{n=1}^{k+1}\frac{n}{(n+1)!} = 1-\frac{1}{(k+2)!}$

$\sum_\limits{n=1}^k\frac{n}{(n+1)!}+\frac{(k+1)}{(k+2)!}$

$1-\frac{1}{(k+1)!}+\frac{(k+1)}{(k+2)!}$(By the inductive hypothesis.)

$1-\frac{1}{(k+2)!}$

$\endgroup$
2
$\begingroup$

You can simply write it like this also this solution doesn't need induction:

$=\frac{2-1}{2!}+\frac{3-1}{3!}+\frac{4-1}{4!}+...+\frac{n+1-1}{(n+1)!}$

$=1-\frac{1}{2!}+\frac{1}{2!}-\frac{1}{3!}+...+\frac{1}{n!}-\frac{1}{(n+1)!}$

$=1-\frac{1}{(n+1)!}$

$$solved!$$

$\endgroup$
1
  • $\begingroup$ Good observation to see that the sum telescopes. But, to be precise, what happens inside the $\ldots$ on your second formula is the induction :-). In some sense all sum formulas proved by induction have this same structure. You can write the textbook proofs of for example the formulas $$\sum_{k=1}^nk=\frac{n(n+1)}2,\quad\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}6$$ in this way as well, but yet we should call these proofs proofs by induction. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 10, 2016 at 9:19

Not the answer you're looking for? Browse other questions tagged .