Evaluate $\frac{1}{(1+1)!} + \frac{2}{(2+1)!}+...+\frac{n}{(n+1)!}$. This is from a combinatorics textbook so I'd like a combinatorial proof. I find doing this kind of problem difficult especially when you have to sum - I don't know how to construct a sensible analogy using the addition principle.
Similar question that appears just before this question in the text: Combinatorics problem involving series summation
On
Using generating functions, which are widely used in combinatorics: $$a_n=\sum\limits_{k=1}^{n}\frac{k}{(k+1)!}$$ which is the same as $$a_n=a_{n-1}+\frac{n}{(n+1)!}$$ with generating function $$f(x)=\sum\limits_{n}\color{red}{a_n}x^n =a_0+\sum\limits_{n=1}\left(a_{n-1}+\frac{n}{(n+1)!}\right)x^n=\\ a_0+x\sum\limits_{n=1}a_{n-1}x^{n-1}+\sum\limits_{n=1}\frac{n}{(n+1)!}x^n=\\ a_0+xf(x)+\sum\limits_{n=1}\frac{n+1}{(n+1)!}x^n-\sum\limits_{n=1}\frac{1}{(n+1)!}x^n=\\ a_0+xf(x)+\left(\sum\limits_{n=1}\frac{1}{(n+1)!}x^{n+1}\right)'-\frac{1}{x}\sum\limits_{n=1}\frac{1}{(n+1)!}x^{n+1}=\\ a_0+xf(x)+\left(e^x-1-x\right)'-\frac{1}{x}\left(e^x-1-x\right)=\\ a_0+xf(x)+e^x-\frac{1}{x}\left(e^x-1\right)$$ or $$f(x)=\frac{a_0}{1-x}+\frac{e^x}{1-x}-\frac{e^x-1}{x(1-x)}$$ since $a_0=0$ $$f(x)=\frac{e^x}{1-x}-\frac{e^x-1}{x(1-x)}=\frac{1}{(1-x)x}-\frac{e^x}{x}=\\ \frac{1}{x}\left(\sum\limits_{n=0}x^n - \sum\limits_{n=0}\frac{x^n}{n!}\right)=\sum\limits_{n=1}\color{red}{\left(1-\frac{1}{(n+1)!}\right)}x^{n}$$ as a result $$a_n=1-\frac{1}{(n+1)!}, n\geq1$$
Consider a uniformly at random selected permutation of $\{1,2,\dots,n,n+1\}$.
The probability that $2$ appears before $1$ is $\frac{1}{(1+1)!}$
Given that this does not occur, then $1$ and $2$ appear in the correct order. The probability then that $3$ appears before at least one of $2$ or $1$ as well as $1$ and $2$ appearing in the correct order is $\frac{2}{(2+1)!}$.
Given that this does not occur, then $1,2,3$ all appear in the correct order. The probability then that $4$ appears before at least on of $3,2,1$ and $1,2,3$ all appearing in the correct order is $\frac{3}{(3+1)!}$...
...
Given that this does not occur, then $1,2,3,\dots,n$ all appear in the correct order. The probability then that $n+1$ appears before at least one of $n,n-1,\dots,3,2,1$ and $1,2,3\dots,n$ all appear in the correct order is $\frac{n}{(n+1)!}$
Given that this does not occur, then $1,2,3,\dots,n,n+1$ all appear in the correct order. This occurs with probability $\frac{1}{(n+1)!}$
Note that these are all mutually exclusive and exhaustive events, so they add up to equal $1$. Note further that the sum you are interested in is the sum of all of the events except the last one. We have then
$$\frac{1}{(1+1)!}+\frac{2}{(2+1)!}+\dots+\frac{n}{(n+1)!}=1-\frac{1}{(n+1)!}$$
Rephrased, by multiplying the expression by $(n+1)!$, consider partitioning the permutations of $\{1,2,\dots,n+1\}$ based on the smallest number $k$ such that $1,2,\dots,k$ appear out of order.
That is to say, if $k$ is the smallest number such that $1,2,\dots,k$ appear out of order then $1,2,\dots,k-1$ must appear in order while $k$ does not appear after $1,2,\dots,k-1$. To count how many permutations satisfy this condition first pick the spaces that $1,2,\dots,k-1,k$ occupy simultaneously and then pick which of those positions $k$ occupies noting that it cannot be the last. $1,2,\dots,k-1$ appear in their normal order in the remaining selected positions. Then all other elements are distributed among the other spaces. This occurs in
$$\binom{n+1}{k}(k-1)(n+1-k)!=\frac{(n+1)!}{k!(n+1-k)!}(k-1)(n+1-k)!=\frac{k-1}{k!}(n+1)!$$
which you should recognize as following the sequence $0,\frac{1}{2!},\frac{2}{3!},\frac{3}{4!},\frac{4}{5!},\dots$ with the additional factor of $(n+1)!$ which we introduced earlier, otherwise mimicking the desired sum.
By including also the additional case of the identity permutation, the above forms a partition of the permutations of $\{1,2,\dots,n+1\}$. It follows that their respective totals add up to $(n+1)!$.
By removing the identity permutation as well as dividing by the factor of $(n+1)!$ that we introduced, this yields the desired identity
$$\frac{1}{(1+1)!}+\frac{2}{(2+1)!}+\dots+\frac{n}{(n+1)!}=1-\frac{1}{(n+1)!}$$