Prove that $\binom{n}{1}^2+2\binom{n}{2}^2+\cdots +n\binom{n}{n}^2=n\binom{2n-1}{n-1}$

Question

Prove that $$ \binom{n}{1}^2+2\binom{n}{2}^2+\cdots + n\binom{n}{n}^2 = n \binom{2n-1}{n-1}. $$

So $$ \sum_{k=1}^n k \binom{n}{k}^2 = \sum_{k=1}^n k \binom{n}{k}\binom{n}{k} = \sum_{k=1}^n n \binom{n-1}{k-1} \binom{n}{k} = n \sum_{k=0}^{n-1} \frac{(n-1)!n!}{(n-k-1)!k!(n-k-1)!(k+1)!} = n^2 \sum_{k=0}^{n-1} \frac{(n-1)!^2}{(n-k-1)!^2k!^2(k+1)} =n^2 \sum_{k=0}^{n-1} \binom{n-1}{k}^2\frac{1}{k+1}. $$ I do not know what to do with $\frac{1}{k+1}$, how to get rid of that.

Answer 1

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

Applying Vandermonde's identity in third equality.

Answer 2

A combinatorial proof:

We have $n$ men and $n$ women and I want to choose a $n$-person committee and a committee president among those, with the condition that the president must be a woman.

One way to do that is to choose a president among the $n$ women and then choose $n-1$ committee members from the remaining $2n-1$ persons.

So that way gives $n \binom{2n-1}{n-1}$ ways, the right hand side.

On the other hand I can split the count on the number of women in the committee, so there can be $i=1,2,\ldots,n$ many women.

To count those for a fixed $i$, first pick the $i$ women in $\binom{n}{i}$ ways, pick the president among those in $i$ ways, and then pick the men in $\binom{n}{n-i} = \binom{n}{i}$ ways. So for a fixed $i$ we have $i \binom{n}{i}^2$ committees with $i$ women. Summing them gives us the left hand side.

Answer 3

$$k \binom nk^2=\binom nk\cdot k\binom nk$$

For $k\ge1,$ $$k\binom nk=k\cdot\dfrac{n!}{k!\cdot(n-k)!}=n\dfrac{(n-1)!}{(k-1)!\{n-1-(k-1)\}!}=n\binom{n-1}{k-1}$$

Now in the identity $(1+x)^{2n-1}=(x+1)^n(1+x)^{n-1},$ compare coefficients of $x^n$

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

Answer 4

We present a slight variation using formal power series and the coefficient-of operator. Starting from

$$\sum_{k=1}^n k {n\choose k}^2 = \sum_{k=1}^n k {n\choose k} [z^{n-k}] (1+z)^n \\ = [z^n] (1+z)^n \sum_{k=1}^n k {n\choose k} z^k = n [z^n] (1+z)^n \sum_{k=1}^n {n-1\choose k-1} z^k \\ = n [z^n] z (1+z)^n \sum_{k=0}^{n-1} {n-1\choose k} z^k = n [z^{n-1}] (1+z)^n (1+z)^{n-1} \\ = n [z^{n-1}] (1+z)^{2n-1} = n \times {2n-1\choose n-1}$$

which is the claim.