How can I calculate the value of such a sum?

$\sum_{k=0}^{n} (2k^2-3k+1){n\choose k}$

Should I split it into three sums? But then I don't know what to do with $k^2{n\choose k}$. I know that $\sum_{k=0}^{n}{n\choose k} = 2^n$. But that isn't much help, is it? Or maybe I should use generating function? Then $\sum_{k\ge0} {n\choose k} x^k = (1+x)^n$

Please, help.

Thank you.

  • 1
    $\begingroup$ consider $\sum x^k \left({n \atop k}\right)$ and differentiate. $\endgroup$ – Maesumi Jan 26 '13 at 21:25
  • $\begingroup$ Nice, thanks a lot. $\endgroup$ – Hagrid Jan 26 '13 at 21:41
  • $\begingroup$ I don't see it that clearly: differentiating wrt $\,x\,$ gives $\,\sum_{k=1}^nkx^{k-1}\binom{n}{k}\,$....How does this help with $\,2\sum_{k=0}^nk^2\binom{n}{k}\,$ , for example? $\endgroup$ – DonAntonio Jan 26 '13 at 22:06
  • $\begingroup$ I think you need to differentiate it and then multiply by x, then differentiate it again and again multiply by x. $\endgroup$ – Hagrid Jan 26 '13 at 22:08
  • $\begingroup$ just for you to check answer it should be $2^{n-1}(n^2-2n+2)$ $\endgroup$ – mez Jan 26 '13 at 22:19

The following facts may be helpful:

(a) $\dbinom{n}{k}=\dbinom{n}{k}$;

(b) $k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$;

(c) $k(k-1)\dbinom{n}{k}=n(n-1)\dbinom{n-2}{k-2}$.

Now express $2k^2-k+1$ as a linear combination of $1$, $k$, and $k(k-1)$.

  • $\begingroup$ So the solution is $2n(n-1) \cdot 2^{n-2} -n \cdot 2^{n-1} + 2^n$ ? $\endgroup$ – Hagrid Jan 26 '13 at 22:34
  • $\begingroup$ Yes, that's what I get. Simple, eh? Linear algebra can be useful! $\endgroup$ – André Nicolas Jan 26 '13 at 22:42
  • $\begingroup$ Yes, very useful, indeed. Thanks a lot. I was planning to use generating functions, but what you came up with is a lot simpler and quicker :) $\endgroup$ – Hagrid Jan 26 '13 at 22:53
  • $\begingroup$ Generating functions give a very nice approach. But variety is a good thing. $\endgroup$ – André Nicolas Jan 26 '13 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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