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.

Prove that: $$\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$$ i know that: $$\sum_{k=0}^n {n \choose k} = {2^n}$$ how to get the (n + n^2)?

share|improve this question

6 Answers 6

up vote 1 down vote accepted

Alternative proof using no calculus, no combinatorics, just pure algebraic manipulation starting from the special case of the binomial theorem: $$\sum_{k=0}^n \binom{n}{k} = 2^n.$$ We also note the identity $$\begin{align*} \binom{k}{r} \binom{n}{k} &= \frac{k!}{r! \, (k-r)!} \cdot \frac{n!}{k! \, (n-k)!} = \frac{n!}{r! \, (n-r)!} \cdot \frac{(n-r)!}{(k-r)! \, (n-k)!} \\ &= \binom{n}{r} \binom{n-r}{k-r}. \end{align*}$$

Then $$S_1 = \sum_{k=0}^n k \binom{n}{k} = \sum_{k=1}^n \binom{k}{1}\binom{n}{k} = \binom{n}{1} \sum_{k=1}^n \binom{n-1}{k-1} = n 2^{n-1}.$$

Similarly, $$S_2 = \sum_{k=0}^n k(k-1) \binom{n}{k} = 2 \sum_{k=2}^n \binom{k}{2} \binom{n}{k} = 2 \binom{n}{2} \sum_{k=2}^n \binom{n-2}{k-2} = n(n-1) 2^{n-2}.$$

Consequently, $$\sum_{k=0}^n k^2 \binom{n}{k} = S_1 + S_2 = n(n+1)2^{n-2}.$$ In this manner, we can recursively evaluate sums of the form $$\sum_{k=0}^n k^m \binom{n}{k},$$ using the general identity $$\sum_{k=r}^n \binom{k}{r}\binom{n}{k} = \binom{n}{r} 2^{n-r}.$$

share|improve this answer

Hint: The derivative of $(1+x)^n = \sum_{k=0}^n {n \choose k} x^k$ with respect to $x$ is $\sum_{k=0}^n k {n \choose k} x^{k-1}$. Can you see how to apply this twice and combine results to get your identity with $x = 1$?

share|improve this answer
1  
This has a finite calculus feel to it. I like it :) –  Cameron Williams Apr 13 at 20:19

We have a group of $n$ people in a class. We want to choose $1$ or more of them to go on a special trip. And we want to appoint one of the people who goes on the trip Leader, and one of the people Treasurer, where Leader and Treasurer could be the same.

Then the number of ways to choose the people who will go on the trip, and assign the special awards, is $\sum_1^n k^2\binom{n}{k}$. (Whether we start summing at $0$ or $1$ does not matter.)

We count the ways to do the choosing in another way. We can choose $1$ person to be both Leader and Treasurer, and then choose a subset of the rest to also go on the trip. There are $n2^{n-1}$ ways to do this. Or else we can choose different people to be Leader and Treasurer, and get a subset of the rest to join them. This can be done in $n(n-1)2^{n-2}$ ways.

Add. We get $(n)2^{n-1}+n(n-1)2^{n-2}=(2n)2^{n-2}+n(n-1)2^{n-2}=(n^2+n)2^{n-2}$.

share|improve this answer

Differentiating the binomial expansion $$ (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k, $$ we obtain $$ n(1+x)^{n-1}=\sum_{k=0}^n k\binom{n}{k}x^{k-1} \quad\Longrightarrow\quad n2^{n-1}=\sum_{k=0}^n k\binom{n}{k} \tag{1} $$ and $$ n(n-1)(1+x)^{n-2}=\sum_{k=0}^n k(k-1)\binom{n}{k}x^{k-2} \Longrightarrow\ n(n-1)2^{n-2}=\sum_{k=0}^n k(k-1)\binom{n}{k}. \tag{2} $$ Adding $(1)$ and $(2)$ we obtain $$ n(n+1)2^{n-2}=\sum_{k=0}^n k^2\binom{n}{k}. $$

share|improve this answer

How about a solution with combinatorial interpretation?

For any given subset of $n$, choose $k$ elements, then choose $2$ elements from this $k$-subset in an independent way. This is how we can look on the left side of the equation. There are $2$ ways of doing this:

  • either we choose the same element twice, or
  • we choose different elements,

Hence the addition $n^2 + n$ on the right side.

share|improve this answer

Its a bit easiler to evaluate up to $n+1$.

I will use the identity that $\dbinom{a}k = \frac{a}k \dbinom{a-1}{k-1}$.

$\sum_{k = 0}^{n+1} k^2 \dbinom{n+1}k$

$ = 0+1 \dbinom{n+1}1 + 4 \dbinom{n+1}2 + 9 \dbinom{n+1}3 + \cdots + (n+1)^2 \dbinom{n+1}{n+1}$

$ = 0+(n+1) \dbinom{n}0 + 2(n+1) \dbinom{n}1 + 3 \dbinom{n}2 + \cdots + (n+1) \dbinom{n}n$

$ = (n+1) \left( \sum_{k = 0}^{n} (k+1) \dbinom{n}k \right)$.

This can be easily evaluated from the derivative of $x(1+x)^n$.

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.