Approach to find partial sum formula

Question

The partial sum formula for $$\displaystyle \sum_{k=1}^n \dfrac{k}{(k+1)!}$$ is given by $$1-\dfrac{1}{(n+1)!}$$ I'm interested in the approach to reach there. How do you prove it without induction?

Answer 1

Note that $\frac k{(k+1)!}=\frac{(k+1)-1}{(k+1)!}=\frac1{k!}-\frac1{(k+1)!}$. Therefore, your sum is a telescopic sum.

Answer 2

Here is a probabilistic proof. Let $[n]:=\{0,1,2,\ldots,n\}$. Consider the set $S$ of all permutations on $[n]$. Equip $S$ with the uniform discrete probability measure $\mathbb{P}$. The event $E$ that a randomly picked permutation $\Sigma$ is not the identity clearly has the probability of $$1-\frac{1}{(n+1)!}\,.$$

Now, we argue this way. For $k=1,2,\ldots,n$, let $E_k$ denote the event that $$\Sigma(0)<\Sigma(1)<\Sigma(2)<\ldots<\Sigma(k-1)\text{ but }\Sigma(k)<\Sigma(k-1)\,.$$ Then, prove that $E_1,E_2,\ldots,E_n$ are pairwise disjoint events, $\displaystyle\bigcup_{k=1}^n\,E_k=E$, and $$\mathbb{P}\left(E_k\right)=\frac{k}{(k+1)!}\,.$$