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.

Possible Duplicate:
Crazy induction

I'm in urgent need of help solving this proof. I have my final exam tomorrow, and me passing depends on me being able to understand how to prove this statement, and similar statements. Can anyone explain to me how this is proved?

$$\displaystyle \sum_{i = 0}^n {n \choose i}{i^2}= (n+1)(n){2^{n-2}}$$ for n$\ge0$

share|improve this question
    
That title @Marvis –  Jean-Sébastien Dec 10 '12 at 19:42
add comment

marked as duplicate by Marvis, amWhy, Mike Spivey, draks ..., Davide Giraudo Dec 10 '12 at 20:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

We know the nbinomial expansion $$f(x):=\sum_{i=0}^n {n\choose i}x^i = (1+x)^n.$$ Note that taking the derivative and multiplying by $x$ turns $x^i$ into $ix^i$, thus $$xf'(x)=\sum_{i=0}^n {n\choose i}ix^i$$ and repeating this step $$x (f'(x)+xf''(x))=\sum_{i=0}^n {n\choose i}i^2x^i$$ We want this evaluated at at $x=1$. With $f'(x) = n(1+x)^{n-1}$ and $f''(x)=n(n-1)(1+x)^{n-2}$, we obtain $$ 1\cdot(n2^{n-1}+1\cdot n(n-1)2^{n-2})=n(n-1+2)2^{n-2}=n(n+1)2^{n-2}.$$

share|improve this answer
    
Thank you very much for the quick answer, but the course I am taking does not use derivatives until next semester, and I am expected to prove this without them. Your reasoning above seems adequate for solving this problem, but is it possible that there is a solution that leaves calculus out of it? –  user52527 Dec 10 '12 at 20:11
add comment

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