Give a combinatorial proof to show the following for all integers $n \geq 2$.

Question

$$2^{n-2} n (n -1) = \sum\limits_{k=2}^n k (k - 1) \binom{n}{k}.$$

I'm completely stumped. I just have no idea how to do this. What I've tried so far has been simplifying the right hand side slightly to $\sum\limits_{k=2}^n \binom{n}{k - 2}$, and then proving that this somehow is equal to some manipulation of the left hand side. I can't seem to find any breakthroughs that way though.

If anyone could help out or point me in the right direction that would be great.

EDIT: I've actually just realized my simplification of the right hand side is wrong. Now I'm even more stuck.

Answer 1

On the right side, you pick a number $k$ in $\{2,3,4,\ldots,n\}$, then pick a subset of size $k$ from the pool of size $n$ candidates, then you choose a president and a vice-president from among the $k$ chosen members.

On the left side, you first pick a president and vice president from the pool of $n$ candidates, then from among the remaining $n-2$ members, you pick the other members of the privileged subset.

Answer 2

$$ \sum\limits_{k=2}^n k (k - 1) \binom{n}{k}=\sum\limits_{k=2}^n k (k - 1)\frac{n!}{k!(n-k)!}=n(n-1)\sum\limits_{k=2}^n\frac{(n-2)!}{(k-2)!(n-k)!}=2^{n-2}n(n-1)$$ [Because $(1+x)^{n-2}=\sum\limits_{k=2}^n\frac{(n-2)!}{(k-2)!(n-k)!}x^{k-2}$, now put $x=1$ ]