11
$\begingroup$

A friend of mine put me a problem some time ago, and after trying to do it, I finally surrendered. I looked for the answer online so maybe I could guess why is it like it is, but I just can't understand anything about it. Could someone explain, rather using logic, why is the identity as it is?

$$\sum_{k=0}^n {n \choose k}k^2 = 2^{n-2}n(n+1)$$

$\endgroup$
29
$\begingroup$

Here is a counting argument for why this identity holds. Suppose you have a population of $n$ people. Out of this group of people, you want to count the number of ways to create a club that has a president and a treasurer (the president and treasurer could be the same person). The club does not need to include all $n$ people.

One way to count the number of ways to create this club is to 1) Sum over the size of the club. 2) Pick the people to be in the club. 3) Pick the president. 4) Pick the treasurer.

So if the club has size $k$, then there are ${n \choose k}$ ways to choose the club and then $k$ choices for the president and $k$ choices for the treasurer. Overall, there are $$ \sum_{k =0}^n {n \choose k} k^2 $$ such ways.

Conversely, we can 1) Choose the president first (out of $n$ people). 2) Choose the treasurer. 3) Pick the remaining members of the club.

There are $n$ ways to pick the president. Now for the treasurer, we either pick (a) the president or (b) one of the $n-1$ other people. If we pick the president as the treasurer, then each of the remaining $n-1$ people are either in the club or not; as a result, there would be $2^{n-1}$ ways to pick these members in this case. Now if we chose a different person as the treasurer, then each of the remaining $n-2$ people are either in the club or not; as a result, there would be $2^{n-2}$ ways to pick these members. Thus, overall there are $$ n \cdot 1 \cdot 2^{n-1} + n \cdot (n-1) \cdot 2^{n-2} = n(n+1)2^{n-2} $$ ways to select the club.

$\endgroup$
  • 3
    $\begingroup$ No doubt you could extend this to $\displaystyle \sum_{k=0}^n {n \choose k}k^3 = 2^{n-3}n^2(n+3)$ but I suspect it might get a little tiring for higher powers $\endgroup$ – Henry Jun 3 '16 at 20:59
24
$\begingroup$

We have: $$(1+x)^n=\sum_0^n \binom nk x^k$$

Differentiate to get: $$n(1+x)^{n-1}=\sum_1^n \binom nk kx^{k-1}$$

Multiply by $x$ to get: $$nx(1+x)^{n-1}=\sum_1^n \binom nk kx^{k}$$

Differentiate again to get $$n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2}=\sum_1^n \binom nk k^2x^{k-1}$$

Now let $x=1$ to get the desired result. (note that the summand vanishes if $k=0$ so you can start the sum at $k=0$ without changing the right hand).

$\endgroup$
  • 1
    $\begingroup$ Thank you, this was the answer I was looking for. $\endgroup$ – user334765 Jun 3 '16 at 20:38
1
$\begingroup$

Another method.
Without using calculus. $$\begin{align} \sum_{k=0}^n\binom nk k^2&= n\sum_{k=1}^n\binom{n-1}{k-1}k\\ &=n\sum_{k=0}^{n-1}\binom{n-1}{k}(k+1)\\ &=n\left[\sum_{k=0}^{n-1}\binom {n-1}k k+\binom {n-1}k\right]\\ &=n\left[(n-1)\sum_{k=1}^{n-2}\binom{n-2}{k-1}+\sum_{k=1}^{n-1}\binom{n-1}k\right]\\ &=n\bigg[(n-1)2^{n-2}+2^{n-1}\bigg]\\ &=2^{n-2}\ n(n+1)\qquad\blacksquare \end{align}$$

$\endgroup$
1
$\begingroup$

By definition,

$$\binom nk=\frac{n!}{k!(n-k)!},$$ so that

$$\binom nkk=\frac{n!}{(k-1)!(n-k)!}==\frac{n(n-1)!}{(k-1)!((n-1)-(k-1))!}=\binom {n-1}{k-1}n.$$

This trick allows you to "absorb" the factor $k$ inside the binomial number.

The trick doesn't work with $k^2$ because the denominator doesn't have a second factor $k$, but it does work with $k^2-k$:

$$\binom nkk(k-1)=\frac{n!}{(k-2)!(n-k)!}==\frac{n(n-1)(n-2)!}{(k-2)!((n-2)-(k-2))!}=\binom {n-2}{k-2}n(n-1).$$

Adding these two results and summing over $k$,

$$S=2^{n-1}n+2^{n-2}n(n-1)=2^{n-2}n(n+1).$$


Check with $n=5$.

$$\begin{align}k&\to\color{blue}1\cdot0+\color{blue}5\cdot1+\color{blue}{10}\cdot2+\color{blue}{10}\cdot3+\color{blue}5\cdot4+\color{blue}1\cdot5=2^4\cdot 5=80\\ k^2-k&\to\color{blue}1\cdot0\cdot\bar1+\color{blue}5\cdot1\cdot0+\color{blue}{10}\cdot2\cdot1+\color{blue}{10}\cdot3\cdot2+\color{blue}5\cdot4\cdot3+\color{blue}1\cdot5\cdot4=2^3\cdot 5\cdot4=160\end{align}$$

and summing,

$$k^2\to\color{blue}1\cdot0^2+\color{blue}5\cdot1^2+\color{blue}{10}\cdot2^2+\color{blue}{10}\cdot3^2+\color{blue}5\cdot4^2+\color{blue}1\cdot5^2=2^3\cdot 5\cdot6=240.$$

$\endgroup$

Your Answer

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