3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.