# Evaluating the sum $\sum\limits_k \ k\binom{n}{k}^2$ using generating functions

I have to evaluate this expression $\sum\limits_k \ k\binom{n}{k}^2$ using generating function. Could you help me please? Also with some hints.

-

I suggest that you interpret the sum as the convolution of the generating function with coefficents $k\binom{n}{k}$ and $\binom{n}{k}$.

-

Suppose we are trying to evaluate $$\sum_{k=0}^n k {n\choose k}^2.$$

Note that $$k{n\choose k} = \frac{n!}{(k-1)! (n-k)!} = n \frac{(n-1)!}{(k-1)! (n-k)!} = n{n-1 \choose k-1}.$$

This means the sum is in fact $$n\sum_{k=1}^n {n\choose k} {n-1\choose k-1}.$$

Introduce the integral representation $${n-1\choose k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z^k} \; dz.$$

Observe that the the integrand is entire when $k=0$ so we may extend the sum at its lower limit to include zero, getting $$\frac{n}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \sum_{k=0}^n {n\choose k} \frac{1}{z^k} \; dz \\ = \frac{n}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \left(1+\frac{1}{z}\right)^n \; dz \\ = \frac{n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-1}}{z^n} \; dz.$$

This can be evaluated by inspection and produces the result $$n \times [z^{n-1}] (1+z)^{2n-1} = n\times {2n-1\choose n-1} = n\times {2n-1\choose n}.$$

-