How could I have found the closed form of $\sum_{k=1}^n \frac{k}{(k+1)!}$ in advance?

Question

If you calculate the first three sums, a pattern becomes clear revealing the closed form which is easily proven by induction:

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

I’ve been trying to find the closed form without calculating the first few sums, but failed in doing so. I wonder if there is a way to find the closed form in advance or to lead it back to the closed form of some other well-known series. Is there maybe a combinatorial way to think about it?

Answer 1

Using telescoping sum:

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

Answer 2

There are various ways that (perhaps in hindsight) we can see that the formula is correct "without algebra." We describe one approach in detail, and mention another (the Cantor Factorial Notation) in a brief remark at the end.

My favourite approach is probabilistic, and unfortunately takes a number of words to explain. We have $n+1$ objects, say the integers from $0$ to $n$, and we permute them at random. There are $(n+1)!$ permutations of these numbers, of which only $1$ is in the correct order, so the probability our numbers are not in correct order is $1-\frac{1}{(n+1)!}$. That is the right-hand side of our identity.

The probability that $0$ and $1$ are not in correct relative order (that is, $1$ comes before $0$ in the permutation) is $\frac{1}{2!}$.

The probability that $0$ and $1$ are in correct relative order but $0$, $1$, and $2$ are not is $\frac{2}{3!}$. For there are $3$ places where $2$ could be relative to $0$ and $1$, and $2$ of them give the wrong relative order.

The probability that $0$, $1$, and $2$ are in the correct relative order but $3$ is not is $\frac{3}{4!}$. For there are $4!$ possible relative orderings of our $4$ numbers. If we write down $0$, $1$, and $2$ with a little gap between them, this determines $4$ "gaps." These are the gap between $0$ and $1$, the gap between $1$ and $2$, and the two "endgaps." Placing $3$ is $3$ of these gaps produces the wrong relative order of our $4$ numbers.

And so on. The probability that the numbers $0$ to $k-1$ are in the correct relative order, but the numbers $0$ to $k$ are not, is by the same "gaps" argument equal to $\frac{k}{(k+1)!}$. Summing from $1$ to $n$ yields the right-hand side.

Remark: Another way of explaining the identity involves Cantor's Factorial Notation for the reals. It turns out that our identity is correct for basically the same reason as the reason that $0.9999$ is $1-\frac{1}{10^4}$. The idea of the factorial notation can be extended to a broader notion that includes both base $b$ notation and factorial notation. For this generalization, there is an identity corresponding to the identity asked about by the OP.