Jtdylktuy

Prove that
$$
binom{n}{1}^2+2binom{n}{2}^2+cdots + nbinom{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}^2frac{1}{k+1}.
$$
I do not know what to do with $frac{1}{k+1}$, how to get rid of that.

$$sum_{k=1}^{n}kbinom{n}{k}^{2}=nsum_{k=1}^{n}binom{n-1}{k-1}binom{n}{n-k}=nsum_{k=0}^{n-1}binom{n-1}{k}binom{n}{n-k-1}=nbinom{2n-1}{n-1}$$

Applying Vandermonde's identity in third equality.

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.

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

$$sum_{k=1}^n k {nchoose k}^2
= sum_{k=1}^n k {nchoose k} [z^{n-k}] (1+z)^n
\ = [z^n] (1+z)^n sum_{k=1}^n k {nchoose k} z^k
= n [z^n] (1+z)^n sum_{k=1}^n {n-1choose k-1} z^k
\ = n [z^n] z (1+z)^n sum_{k=0}^{n-1} {n-1choose 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-1choose n-1}$$

which is the claim.

$$k binom nk^2=binom nkcdot kbinom nk$$

For $kge1,$ $$kbinom nk=kcdotdfrac{n!}{k!cdot(n-k)!}=ndfrac{(n-1)!}{(k-1)!{n-1-(k-1)}!}=nbinom{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}^nbinom nkbinom{n-1}{k-1}$$