# Proving a Binomial Sum

How do I prove that $$\sum_{r=0}^{n-1}\left[ r \binom{n}{r} \binom{n}{r+1}\right]=n \binom{2n-1}{n-2}$$ without induction?

I've tried manipulating $(1+x)^n$ and the binomial coefficients, but to no avail. Also, how can one explain this identity combinatorially?

• – Lucian Nov 18 '14 at 5:41

Here is a combinatorial proof:
Consider a class of $2n$ students of which $n$ are boys and $n$ are girls.
The right hand side of the given identity is the number of ways of selecting a team of of $n-1$ students with a boy as the team captain.This can be done by first selecting the captain from $n$ boys, which can be done in $\binom{n}{1}=n$ ways and then selecting the remaining $n-2$ team members from the remaining $2n-1$ students, which can be done in $\binom{2n-1}{n-2}$ ways. Therefore, the total number of ways of selecting a team of $n-1$ students with a boy captain is $n\binom{2n-1}{n-2}.$

Each such team consists of $r$ boys and $n-1-r$ girls for some $r$ between $1$ and $n-1.$ Now, in how many ways can we select a team of $r$ boys and $n-1-r$ girls with a boy captain (for each $r=1,2,...,n-1)$? First, select the $r$ boys to be included in the team. This can be done in $\binom{n}{r}$ ways and then designate one of the selected $r$ boys to be the captain, which can be done in $\binom{r}{1} =r$ ways. Now select $n-1-r$ girls from the $n$ girls in the class, which can be done in $\binom{n}{n-1-r} = \binom{n}{n-(n-1-r)} =\binom{n}{r+1}$ ways. Thus, number of team selections with $r$ boys and a boy captain = $r\binom{n}{r}\binom{n}{r+1}$. This is possible for each value of $r$ between $1$ and $n-1$.
Therefore, total number of team selections $=\sum \limits_{r=1}^{n-1} r \binom{n}{r}\binom{n}{r+1} = \sum \limits_{r=0}^{n-1} r \binom{n}{r}\binom{n}{r+1}$

Eliminate $r$ by merging it with the first binomial coefficient, then use symmetry followed by Vandermonde's identity.

\begin{align} \sum_{r=0}^{n-1}r\binom nr\binom n{r+1}&=\sum_{r=0}^{n-1}n\binom{n-1}{r-1}\binom n{r+1}\\ &=n\sum_{r=0}^{n-1}\binom {n-1}{r-1}\binom n{n-r-1}\\ &=n\binom{2n-1}{n-2}\qquad \blacksquare \\\end{align}

By way of enrichment here is another algebraic proof using basic complex variables.

We seek to compute $$\sum_{r=0}^n r {n\choose r} {n\choose r+1}.$$

Introduce the integral representation $${n \choose r+1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{r+2}} \; dz.$$

We use this to obtain an integral for the sum. Note that when $r+2>n+1$ or $r>n-1$ the pole at zero disappears which means that the integral is zero. Therefore we obtain

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{r=0}^n r {n\choose r} \frac{(1+z)^n}{z^{r+2}}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^2} \sum_{r=0}^n r {n\choose r} \frac{1}{z^r}\; dz.$$

Note that $$x \frac{d}{dx} (1+x)^n = \sum_{r=0}^n r {n\choose r} x^r = nx (1+x)^{n-1}.$$

Returning to the integral this gives $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^2} \times n \frac{1}{z} \left(1+\frac{1}{z}\right)^{n-1} \; dz \\ = \frac{n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^3} \frac{(1+z)^{n-1}}{z^{n-1}} \; dz \\ = \frac{n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-1}}{z^{n+2}} \; dz.$$

This last integral can be evaluated by inspection and the result is $$n\times {2n-1\choose n+1} = n {2n-1\choose n-2}.$$