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.

Can this identity be derived from the binomial theorem?

$$n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$$


I tried starting from $2^n = \displaystyle\sum_{i=0}^{n} \binom{n}{i}$ and dividing it by $4$ in order to get $2^{n-2}$.

share|improve this question
4  
Hint: Differentiate $(1+x)^n =\sum_{k=0}^n \binom{n}{k} x^k$ (respect to $x$) twice. –  tetori Feb 14 '13 at 2:35
    

3 Answers 3

up vote 5 down vote accepted

Start with

$$(1+x)^n = \sum_{i=0}^n \binom{n}{i} x^i$$

Take the derivative of both sides:

$$n (1+x)^{n-1} = \sum_{i=1}^n i \binom{n}{i} x^{i-1}$$

Multiply both sides by $x$:

$$n x (1+x)^{n-1}= \sum_{i=1}^n i \binom{n}{i} x^i$$

Take another derivative:

$$n (1+x)^{n-1} + n (n-1) x (1+x)^{n-2} = \sum_{i=1}^n i^2 \binom{n}{i} x^{i-1}$$

Plug in $x=1$ in the above equation:

$$n 2^{n-1} + n (n-1) 2^{n-2} = n (n+1) 2^{n-2} = \sum_{i=1}^n i^2 \binom{n}{i} $$

share|improve this answer

Hint: taking the first two consecutive derivatives

$$(1+x)^n=\sum_{k=0}^nx^k\binom{n}{k}\\n(1+x)^{n-1}=\sum_{k=1}^nkx^{k-1}\binom{n}{k}\\n(n-1)(1+x)^{n-2}=\sum_{k=2}^nk(k-1)x^{k-2}\binom{n}{k}\ldots$$

share|improve this answer

Start from the binomial theorem in the form

$$(x+1)^n=\sum_{k=0}^n\binom{n}kx^k$$

and differentiate with respect to $x$:

$$\begin{align*} n(x+1)^{n-1}&=\sum_{k=0}^n\binom{n}kkx^{k-1}\\\\ &=\sum_{k=1}^n\binom{n}kkx^{k-1}\;. \end{align*}$$

Differentiate again:

$$\begin{align*} n(n-1)(x+1)^{n-2}&=\sum_{k=1}^n\binom{n}kk(k-1)x^{k-2}\\\\ &=\sum_{k=1}^n\binom{n}kk^2x^{k-2}-\sum_{k=1}^n\binom{n}kkx^{k-2}\;. \end{align*}$$

Now let $x=1$ to get

$$\begin{align*} n(n-1)2^{n-2}&=\sum_{k=1}^n\binom{n}kk^2-\sum_{k=1}^n\binom{n}kk\\\\ &=\sum_{k=1}^n\binom{n}kk^2-\sum_{k=1}^n\binom{n-1}{k-1}n\\\\ &=\sum_{k=1}^n\binom{n}kk^2-n\sum_{k=0}^{n-1}\binom{n-1}k\\\\ &=\sum_{k=1}^n\binom{n}kk^2-n2^{n-1}\\\\ &=\sum_{k=1}^n\binom{n}kk^2-2n2^{n-2}\;, \end{align*}$$

and solve for $\displaystyle\sum_{k=1}^n\binom{n}kk^2$ to get the desired result.

share|improve this answer

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.