A combinatorial proof of the identity: $\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$?

Question

Give a combinatorial proof of the identity:

$$\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$$

I am not exactly sure where to start. Since $\binom{n}{k}^2 = \binom{n}{k}\binom{n}{k}$, thus, above equation says that we are choosing k elements out of n elements and we are doing it twice where k starts from 0 and goes all the way to n and we add all of them up. However, about the right side, I have no idea what to say and how it fits in this situation.

Any help will be grately appreciated.

Answer 1

Let there be $n$ girls and $n$ boys, therefore $2n$ people in total, and out of these, you must make a group of $n$ people which contains at least one girl, and appoint one girl from the chosen group the "head" of the group.

In how many ways can this be done?

One way of counting this, is picking that head girl in $n$ ways, and then choosing the rest of the people in the group in $\binom{2n-1}{n-1}$ ways. So that gives the right hand side.

Another way of doing this, is to say,fix the number of girls you want in your group, say $k$. Now, Choose $k$ girls for your group, this is done in $\binom nk$ ways. Exclude $k$ boys out of $n$ from the group you want to make, this is also done in $\binom nk$ ways. Now, the group of girls you chose, along with the non-excluded boys, gives a group of $n$ people. You can choose a head from among the $k$ girls in $k$ ways.

Since the above can be done for every $k=1$ to $n$(this would be a group having only girls) we get $\sum_{k=1}^n k\binom nk^2$(first choose the girls, then exclude the boys, then choose the head girl). Hence, equality follows.

EDIT: A combinatorial proof for any identity is essentially a set whose cardinality can be found in two different ways given the right and left hand sides of the identity, along with the explanations of these countings.

Usually (and therefore not always), a sum involves a break up into cases. For each value the parameter takes, you end up counting some subset of the set at hand (in our case, the disjoint subset is exactly those cases where exactly $k$ girls are there in the group, for each $k$), and these subsets are disjoint and their union is the set.

On the other hand, a combination $\binom mn$ is indicative of "free" choice, and in counting the cardinality free choice often plays a big role, as it did in our case.

Usual proofs involve taking such a set : one way of counting is looking at free choices and putting them together, and another is by breaking into cases and then solving each case, as we did here. Usual tricks for such a set come only with practice, for example the introduction of the "head" girl here.

Answer 2

Further elaboration on JMoravitz's hint (which was posted as I was writing this):

• Rewrite the left-hand side as $\sum_{k=1}^n \binom{n}{k} \binom{n}{n-k}$
• Think of a situation with red balls numbered $1,\ldots,n$ and blue balls numbered $1,\ldots,n$. Think of what outcomes the right-hand side could be counting, and try to categorize the outcomes into $n$ categories in a way that each category $k=1,\ldots,n$ has $k \binom{n}{k} \binom{n}{n-k}$ outcomes.

The right-hand side can be interpreted as the number of ways to select a blue ball to be the "special ball" and then picking $n-1$ other balls from the remaining $2n-1$.

${}$

These scenarios can be categorized by how many blue balls (including the special ball) were selected, which yields the left-hand side. That is, the number of outcomes that have $k$ blue balls is $k \binom{n}{k} \binom{n}{n-k}$, since the number of ways to select $k$ blue balls and $n-k$ red balls is $\binom{n}{k} \binom{n}{n-k}$, and there are $k$ ways to select the "special ball" from the $k$ blue balls.

Answer 3

Consider the set $\{1,2,\dots,2n\}$ and mark one of its even elements. Then choose $n-1$ more out of $2n-1$ other (non-marked) elements in the set. The number of ways to do this is the right-hand side in your equation. Thus, you have chosen $n$ elements out of $2n$, including at least one even element.

Alternatively, you can choose $n$ elements from $\{1,2,\dots,2n\}$ which include at least one even element as follows. For each $k\in[1,n]$, choose $k$ even elements and $n-k$ odd elements, then mark one of the chosen even elements. The number of ways to do this is the left-hand side of your equation.

Thus, both sides count the objects in the same set, so they are equal.

Answer 4

First we can show that $$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$

We can see this easily if we're working with factorials. For the combinatorial proof the left hand side is simply choosing $k$ objects from $n$ objects.

We can do the same on the rhs by first fixing one of the $n$ objects and then picking the rest of the $k-1$ objects from the remaining $n-1$ objects. This gives us $\binom{n-1}{k-1}$ $ { }$ $k$-selections containing our fixed object. Since there are $n$ objects we get a total of $n\binom {n-1}{k-1}$ $ { }$ $k$-selections.

However we can see that each $k$-selection will be repeated $k$ times. This is because fixing each element of a $k$-selection introduces this $k$-selection. Dividing by $k$ gives us $$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$

We can now simplify your expression to give:

\begin{align*}\sum_{k=1}^n k \binom{n}{k}^2 &= \sum_{k=1}^n k \binom{n}{k}\binom{n}{n-k} \\ &= \sum_{k=1}^n n \binom{n-1}{k-1}\binom{n}{n-k} \end{align*}

By disregarding the common factor $n$ we simply have to prove that

$$ \sum_{k=1}^n \binom{n-1}{k-1}\binom{n}{n-k} = \binom{2n-1}{n-1} $$

It is easy to see that we can also select $n-1$ objects from $2n-1$ objects by first choosing $k-1$ objects from a fixed $n-1$ objects then by choosing $n-k$ objects from the remaining $n $ objects. See Chu–Vandermonde identity .