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.
Evaluating the sum $\sum\limits_k \ k\binom{n}{k}^2$ using generating functions
2 Answers
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}.$