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.

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

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|cite|improve this question

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

This question was marked as an exact duplicate of an existing question.

    
That title @Marvis – Jean-Sébastien Dec 10 '12 at 19:42

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|cite|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

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