Combinatorial proof $\sum_{i=1}^n i/(i + 1)! = 1 - 1/(n+1)!\quad\forall n\in\mathbb N$

Question

I am trying to come up with a combinatorial (or at least partly combinatorial) proof of the equation $$\sum_{i=1}^n \frac i{(i + 1)!} = 1 - \frac 1{(n+1)!}\quad\forall n\in\mathbb N$$

I am thinking the right-hand side can be transformed into $\frac {(n + 1)! - 1} {(n + 1)!}$, where the numerator represents the number of permutations of (n + 1) objects minus one particular permutation. The left-hand side then can be transformed into $\frac {n + \sum_{i=1}^{n-1} i(i + 2)(i + 3)...(n + 1)}{(n + 1)!}$, where apparently the numerator should also be equal to that number. I just cannot figure out why.

Answer 1

For any permutation $\sigma$ of $m$ elements, considered as a length-$m$ sequence of integers between $1$ and $n+1$, let $I(\sigma)$ equal the largest integer $I$ such that $1,2,\dots,I$ appear in order in the sequence (ignoring intervening elements). For example, $I(5,4,3,2,1)=1$, $I(5,1,4,3,2) = 2$, $I(1,4,2,5,3)=3$, $I(5,1,2,3,4)=4$, and $I(1,2,3,4,5)=5$. In general $I(\sigma)$ is some integer between $1$ and $m$, inclusive.

The probability that $I(\sigma) \ge i$ is exactly $\frac1{i!}$ (assuming the permutation length in question is at least $i$), since the symmetric group on $i$ elements acts on permutations by permuting wherever $1,\dots,i$ are and leaving the rest alone. Therefore the probability that $I(\sigma) = i$ is exactly $\frac1{i!} - \frac1{(i+1)!} = \frac i{(i+1)!}$.

We now see that the identity $$ \sum_{i=1}^n \frac i{(i+1)!} + \frac1{(n+1)!} = 1 $$ is expressing the probabilities that a permutation $\sigma$ on $n+1$ elements has $I(\sigma)=i$ $(i=1,\dots,n)$ or $I(\sigma)=n+1$.

Answer 2

Note: In case anyone decides to downvote this answer, please leave a comment explaining what I could have done better (that will ensure my next answer would avoid the same pitfalls as this one)

Answer:

If we multiply Left hand side (LHS) by $(n+1)!$ we get a sum of a series of terms whose i'th term is-

$$ T(i)= i*\frac{(n+1)!}{(i+1)!} = i*P(n+1,(n+1)-(i+1)) $$ and $$ LHS * (n+1)! = \sum_{i=1}^n T(i) $$

where $P(j,k)$ represents the number of permutations of $j$ distinct objects taken $k$ at a time.

Putting $x=n+1$, writing '$i$' in the multiplier as $(i+1-1)$ and simplifying -

$$T(i)= ((i+1)-1) * P(x,x-(i+1))$$

$$T(i)= (i+1) * P(x,x-(i+1)) - P(x,x-(i+1))$$

The first term in the above equation can be simplified by using factorial notation, thereby simplifying further -

$$T(i)= P(x,x-i) - P(x,x-(i+1)) $$

Note how $T(i)$ represents the difference between the number of permutations of $x$ objects taken $(x-i)$ objects at one time and taken $(x-i-1)$ objects at another. (Note also that $x-i$ and $x-i-1$ represent consecutive integers that vary in the series of $T(i)$ terms from $n$ to $1$ as $i$ varies from $1$ to $n$)

Therefore, the cumulative sum of all these differences would yield the difference between the highest and lowest number of permutations of $(n+1)$ objects which appear as first and last terms respectively in the $T(i)$ series as $i$ goes from $1$ to $n$.

$$LHS*(n+1)! = \sum_{i=1}^n T(i) = P(n+1,n)-P(n+1,1) = (n+1)!-1$$

Dividing both sides by $(n+1)!$,

$$LHS = 1-\frac{1}{(n+1)!} = RHS$$ which is the desired result.

Hope this helps.

Answer 3

Hint let

$f(r)=\frac{1}{r!}$ and $f(r+1)=\frac{1}{r+1!}$

$f(r)-f(r+1)=\frac{r}{r+1!}$

Answer 4

Consider the $(n+1)!$ permutations $\sigma$ of $\{1,2,\dots,n+1\}$.

Count the number of $\sigma$ such that $\sigma(1)<\sigma(2)<\dots<\sigma(i)$ but $\sigma(i)>\sigma(i+1)$: there are $\frac{(n+1)!}{(i+1)!}$ choices of $\sigma(i+2),\dots,\sigma(n+1)$, and for each such choice, $\sigma(i+1)$ can be any of the remaining $i+1$ numbers except for the largest, and then $\sigma(1),\dots,\sigma(i)$ are determined. So there are $\frac{(n+1)!i}{(i+1)!}$ possibilities.

But there is one $\sigma$ ($\sigma(i)=i$ for all $i$) that is not counted when we sum over $i$, so the sum is $(n+1)!-1$.