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

• I'm not sure whether a combinatoric proof can sum those fractions, but induction shows the sum is $1-1/(n+1)!$.
– J.G.
Jul 7 '18 at 5:36
• @J.G. I linked a similar problem maybe that will help... (didn't help me) Jul 7 '18 at 5:42

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)!}$$

• Hello can you clarify what you mean by the last part: "based on the smallest number k such that 1,2,…,k appear out of order." Jul 7 '18 at 7:12
• @helios321 Added more details. If you are just having difficulty understanding the phrasing I used, perhaps an example will help. $\color{red}{1}5\color{blue}{4}\color{red}{2}6\color{red}{3}$ is an example of a permutation where $\color{blue}{4}$ is the smallest number which occurs out of order since $\color{red}{123}$ appear in the correct order. By "appearing in the correct order" that is not to say they are adjacent, but merely that $1$ appears before $2$, that $2$ appears before $3$, etc... Jul 7 '18 at 16:19
• Thanks I figured it out now. Interesting it seems the expression multiplied by $(n+1)!$ is the same as in this question math.stackexchange.com/questions/2334537/…, both equal $(n+1)!-1$, but the other is counted by fixing the position. Jul 8 '18 at 0:23

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)!}.$$

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$$

• I don't know what the down-voter was up to, but by all means this is a combinatorial proof! Jul 7 '18 at 12:31
• I'm not the downvoter, but usually your kind of proof is considered to be an algebraic one, whereas a combinatoric proof takes a set with known cardinality and constructs a bijection with another set showing the wanted formula or binomial identity. Jul 8 '18 at 14:02
• @MarkusScheuer or you assume that for a set of size $n$ the number of favourable cases is $a_n$ and then try to derive the recurrence for $n+1$ from $n$. And after, solve the recurrence with generating functions. A technique very often used in enumerative combinatorics. Jul 8 '18 at 14:17
• No doubt, this technique is great and I also appreciate it and use it often. The point is, this type of proof is usually not denoted as combinatorial proof. We find for instance in R. P. Stanleys Enumerative Combinatorics in the introductory chapter How to Count: A proof that shows that a certain set $S$ has a certain number $m$ of elements by constructing an explicit bijection between $S$ and some other set that is known to have $m$ elements is called a combinatorial proof or bijective proof. - As we can see the key term denoting a combinatorial proof is bijection. Jul 8 '18 at 14:43