Show $\sum_{i=0}^n{i\frac{{n \choose i}i!n(2n-1-i)!}{(2n)!}}=\frac{n}{n+1}$

Question

How can this identity be proved? $$\sum_{i=0}^n{i\frac{{n \choose i}i!n(2n-1-i)!}{(2n)!}}=\frac{n}{n+1}$$

I encountered this summation in a probability problem, which I was able to solve using alternative methods. However, I am curious if there is a direct way to prove this identity using algebraic or combinatorial techniques.

Note. The identity was verified by Wolfram|Alpha and it agrees with the answer obtained from the other methods.

Answer 1

By noting that

\begin{align*} i \frac{\binom{n}{i} i! n (2n-1-i)!}{(2n)!} \cdot \frac{n+1}{n} &= i \frac{(n+1)! (2n-1-i)!}{(n-i)!(2n)!} \\ &= \frac{\binom{i}{1}\binom{2n-1-i}{n-1}}{\binom{2n}{n+1}}, \end{align*}

it suffices to prove

$$ \sum_{i=0}^{n} \frac{\binom{i}{1}\binom{2n-1-i}{n-1}}{\binom{2n}{n+1}} = 1, \qquad\text{i.e.,}\qquad \sum_{i=0}^{n} \binom{i}{1}\binom{2n-1-i}{n-1} = \binom{2n}{n+1}. $$

However,

• $\binom{2n}{n+1}$ is the number of ways of picking $n+1$ items from $[2n] = \{1, 2, \ldots, 2n\}$, and

• $\binom{i}{1}\binom{2n-1-i}{n-1}$ is the number of ways of picking $n+1$ items from $[2n]$ such that $i+1$ is the second smallest among the chosen items.

Therefore the identity follows.

Answer 2

Supposing we start from

$$\sum_{q=0}^n {n\choose q} \frac{q}{q+1} {2n\choose q+1}^{-1} = \frac{1}{n+1}.$$

The LHS is

$$n \sum_{q=1}^n {n-1\choose q-1} \frac{1}{q+1} {2n\choose q+1}^{-1}.$$

Recall from MSE 4316307 the following identity which was proved there: with $1\le k\le n$

$$\frac{1}{k} {n\choose k}^{-1} = [z^n] \log\frac{1}{1-z} (z-1)^{n-k}.$$

In the present case we get

$$n\sum_{q=1}^n {n-1\choose q-1} [z^{2n}] \log\frac{1}{1-z} (z-1)^{2n-q-1} \\ = n [z^{2n}] \log\frac{1}{1-z} (z-1)^{2n-2} \sum_{q=1}^n {n-1\choose q-1} \frac{1}{(z-1)^{q-1}} \\ = n [z^{2n}] \log\frac{1}{1-z} (z-1)^{2n-2} \left[ 1 + \frac{1}{z-1} \right]^{n-1} \\ = n [z^{2n}] \log\frac{1}{1-z} (z-1)^{n-1} z^{n-1} = n [z^{n+1}] \log\frac{1}{1-z} (z-1)^{n-1}.$$

Apply the identity again (with $k=2$) to get

$$n \frac{1}{2} {n+1\choose 2}^{-1} = \frac{1}{2} n \frac{2}{(n+1)n} = \frac{1}{n+1}.$$

This is the claim.

Answer 3

Left Hand Side

Let $n$ boys and $n$ girls stand in a line. The number of possibilities in which $i$ boys stand in front of the first girl is:

$$ \binom{n}{i}\cdot i!\cdot n\cdot\left(2n-i-1\right)! $$

Therefore, the LHS gives the expected number of boys standing in front of the first girl.

Right Hand Side

Each boy has $\frac{1}{n+1}$ probability of standing in front of all $n$ girls. Using the linearity of expectation, we get the expected value equal to $\frac{n}{n+1}$

Conclusion

LHS and RHS calculate the same thing, so they must be equal:

$$ \sum_{i=0}^{n}i\cdot\frac{\binom{n}{i}\cdot i!\cdot n\cdot\left(2n-i-1\right)!}{\left(2n\right)!} = \frac{n}{n+1} $$