Double Counting Proof of Combinatorial Equation: n,k $\in$ $\mathbb{N}$, n > k

[tylerc1991]

Homework Statement

For some $n, k \in \mathbb{N}$, where $n > k$, prove

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

by using the double counting proof technique.

Homework Equations

The Attempt at a Solution

So we have to find a set of objects such that both the LHS and the RHS of the above equation count the number of objects in this set.

It looks like the RHS of the above equation is easier to work with, so we should find out what the RHS counts, then show that the LHS counts these same objects.

Suppose a committee consists of $n$ women and $n - 1$ men. Say we wish to construct a subcommittee of size $n - 1$ and choose one of the women to be the chief director of this subcommittee. We see that there are

$\binom{n + n - 1}{n - 1} \cdot \binom{n}{1} = n \cdot \binom{2n - 1}{n - 1}$

ways of constructing such a committee and selecting a woman as the chief director. This gives us the RHS of the required equation, and this is where I get stuck. Ideas?

Thank you!

 

[tylerc1991]

So we have to find a set of objects such that both the LHS and the RHS of the above equation count the number of objects in this set.

It looks like the RHS of the above equation is easier to work with, so we should find out what the RHS counts, then show that the LHS counts these same objects.

Suppose a committee consists of $n$ women and $n - 1$ men. Say we wish to construct a subcommittee of size $n - 1$ and choose one of the women to be the chief director of this subcommittee. We see that there are

$\binom{n + n - 1}{n - 1} \cdot \binom{n}{1} = n \cdot \binom{2n - 1}{n - 1}$

ways of constructing such a committee and selecting a woman as the chief director. This gives us the RHS of the required equation, and this is where I get stuck. Ideas?

Thank you!

Got it.

Instead of constructing a $n - 1$ size committee, construct a $n$ size committee and it is easy to see that the LHS equals the RHS.