Evaluate: $\frac{1}{(1+1)!} + \frac{2}{(2+1)!}+...+\frac{n}{(n+1)!}$ using combinatorics. 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
 A: Solution
Notice that$$\frac{k}{(k+1)!}=\frac{(k+1)-1}{(k+1)!}=\frac{1}{k!}-\frac{1}{(k+1)!}.$$
Hence, $$\sum_{k=1}^n \frac{k}{(k+1)!}=\left(\frac{1}{1!}-\frac{1}{2!}\right)+\left(\frac{1}{2!}-\frac{1}{3!}\right)+\cdots+\left(\frac{1}{n!}-\frac{1}{(n+1)!}\right)=1-\frac{1}{(n+1)!}.$$
A: 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)!}$$
A: 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$$
