Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
consider $\sum x^k \left({n \atop k}\right)$ and differentiate. –  Maesumi Jan 26 '13 at 21:25
    
Nice, thanks a lot. –  Hagrid Jan 26 '13 at 21:41
    
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? –  DonAntonio Jan 26 '13 at 22:06
    
I think you need to differentiate it and then multiply by x, then differentiate it again and again multiply by x. –  Hagrid Jan 26 '13 at 22:08
    
just for you to check answer it should be $2^{n-1}(n^2-2n+2)$ –  mez Jan 26 '13 at 22:19
show 1 more comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
So the solution is $2n(n-1) \cdot 2^{n-2} -n \cdot 2^{n-1} + 2^n$ ? –  Hagrid Jan 26 '13 at 22:34
    
Yes, that's what I get. Simple, eh? Linear algebra can be useful! –  André Nicolas Jan 26 '13 at 22:42
    
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 :) –  Hagrid Jan 26 '13 at 22:53
    
Generating functions give a very nice approach. But variety is a good thing. –  André Nicolas Jan 26 '13 at 23:02
add comment

Your Answer

 
discard

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.