Prove $\sum\limits_{k=1}^n \binom{n}{k}k^2=2^{n-2}n(n+1)$ by combinatorial argument.

Question

Prove $\sum\limits_{k=1}^n {n \choose k}k^2=2^{n-2}n(n+1)$ by combinatorial argument.

Answer 1

In how many ways can you form a subcommittee among $n$ people and appoint two roles within it, possibly to the same person? What if you choose who gets the roles first, and then finish the subcommittee? For the latter, simplify $n2^{n-1}+n(n-1)2^{n-2}$ to separately count the cases where the roles do or don't have the same recipient.

Answer 2

$\sum_{i=1}^n \binom{n}{k}k^2$ is the way to choose $k$-subset $T$ of $n$-set $S$, then choose $(a,b)$ with $a,b\in T$.

It is equivalent to

1. choose $a=b\in S_n$ and then choose other elements in $T$, which is $n\cdot 2^{n-1}$.

2. choose the ordered pair $a\neq b\in S_n$ and then choose other elements in $T$, which is $n\cdot (n-1)\cdot 2^{n-2}$.

Then we see $n\cdot 2^{n-1}+n\cdot (n-1)\cdot 2^{n-2}=2^{n-2}\cdot n(n+1)$.