1
$\begingroup$

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)?

$\endgroup$
1
$\begingroup$

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}.$$

$\endgroup$
7
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ This has a finite calculus feel to it. I like it :) $\endgroup$ – Cameron Williams Apr 13 '14 at 20:19
3
$\begingroup$

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}$.

$\endgroup$
3
$\begingroup$

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}. $$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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