Combination proof for $n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\binom{n}{k}$

Question

How can I show that

let $n$ and $k$ be integers. $n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\dbinom{n}{k}$

It seems a bit confusing to me on the left hand side. You have a set of $n$ people on a team and you keep picking $k$ people who will play a match and you pick before that a captain $k^2$.

Answer 1

Both sides of the identity answer the question: "Given $n$ candidate members, how many ways are there to form a committee with a president and treasurer, if the same person is allowed to fill both roles?"

For the right-hand side, you pick $k$ members, and then choose one of them to be president and one to be treasurer. This immediately gives you the sum on the right-hand side.

For the left-hand side, you pick a president and a treasurer from the entire candidate pool, and then select the rest of the committee. There are two ways to do this:

• Pick one person to be president-and-treasurer (in $n$ possible ways). Then, for each of the other $n-1$ candidate members, decide whether they're on the committee or not (in $2^{n-1}$ possible ways). There are a total of $n2^{n-1}$ ways to do this.
• Pick a president (in $n$ possible ways), a treasurer distinct from the president (in $n-1$ possible ways) and decide whether each of the other $n-2$ candidates is on the committee (in $2^{n-2}$ possible ways). There are a total of $n(n-1)2^{n-2}$ ways to do this.

So there are a total of $n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$ ways to make your choices, which completes the proof.

Answer 2

I have seen the exact same problem before in an exam. You know that

$$(1+x)^{n}=\sum\limits_{k=0}^{n}\binom{n}{k}x^k$$

Differentiate both sides twice, do some re-arranging, let x=1 and all should fall into place.

Answer 3

$$\sum_{k=1}^{n}k^2\binom{n}{k}=\sum_{k=1}^{n}k^2\frac{n}{k}\binom{n-1}{k-1}$$ $$=\sum_{k=1}^{n}kn\binom{n-1}{k-1}=n\sum_{k=0}^{n-1}(k+1)\binom{n-1}{k}=$$ $$=n\sum_{k=0}^{n-1}k\binom{n-1}{k}+n\sum_{k=0}^{n-1}\binom{n-1}{k}=$$ $$=n\sum_{k=1}^{n-1}k\frac{n-1}{k}\binom{n-2}{k-1}+n2^{n-1}=$$ $$=n(n-1)\sum_{k=0}^{n-2}\binom{n-2}{k}+n2^{n-1}=$$ $$=n(n-1)2^{n-2}+2n2^{n-2}=n(n+1)2^{n-2}$$

Answer 4

The following is almost combinatorial (bijective). It can be turned into fully bijective.

We are giving out medals to some people out of a group of $n$, $1$ gold, $1$ silver, the rest plastic. Funny rule: the same person might get the gold and the silver, Precious plastics are at most one per person.

The right-hand side counts the number of ways to do this.

We claim that the left-hand side counts the same thing in a different way. We can either choose different people to get the gold and silver, and from the remaining $n-2$ people, choose a subset, possibly empty, to get the plastic. Or we can choose a single person to get the gold, and a subset of the remaining $n-1$ to get the plastic. Thus the number of ways is $n(n-1)2^{n-2}+n2^{n-1}$. A little algebra shows this is $n(n+1)2^{n-2}$.

Remark: One can make up a story to replace the algebra step by a bijective step.

Answer 5

The number of arbitrary sized team (non empty) you can form from $n$ people and declare a captain and a fund raiser (both can be the same person) among them in $\sum_{k=1}^{n}k^2\dbinom{n}{k}$.

Again you can perform the same task by choosing the captain and the fund raiser among $n$ people plus $1$ dummy in $n+1 \choose 2$ way and choosing the remaining team in $2^{n-1}$ ways.

Therefore, $\sum_{k=1}^{n}k^2\dbinom{n}{k}= {n+1 \choose 2}2^{n-1}$.