Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 7 down vote accepted

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

share|cite|improve this answer

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}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.