Take the 2-minute tour ×

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


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
