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

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

• What is $*$ here? Is it multiplication? – user152715 Sep 27 '14 at 21:46
• Yes, but @Michael Hardy cleaned it up for me to remove ambiguity anyways. – user176049 Sep 27 '14 at 21:47
• Notice that you can type $2\cdot3$ or $2\times3$. You don't need to write $2*3$. The use of an asterisk for that is a workaround for situations where you can use only the symbols on the keyboard. – Michael Hardy Sep 27 '14 at 21:51
• I see user152715 has posted an algebraic argument, in contrast to my combinatorial argument. Usually I prefer understanding it combinatorially. – Michael Hardy Sep 27 '14 at 21:52

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.

• I think I almost understand the explanation for the left hand side now. Would I be correct in thinking that the $2^{n-2}$ is the result of every member not the "president" or "vice president" having two possible combinations of either being in or out of the chosen set? Additionally, I'm having trouble seeing how this encompasses all possible subsets, which the right hand seems to incorporate through inclusion of the summation. – user176049 Sep 27 '14 at 21:56
• That is correct. The total number of subsets of a set of size $n-2$ is $2^{n-2}$. ${}\qquad{}$ – Michael Hardy Sep 27 '14 at 21:58
• Thank you. I see now how these two sides relate. I'm choosing yours as the accepted answer since I agree with you--it is helpful to solve a combinatorial proof in a combinatorial fashion. – user176049 Sep 27 '14 at 22:00

$$\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$ ]

• Can you show me how that final summation is equal to $2^{n - 2}$? I can see how you pulled out the $n(n -1)$, but that last bit seems like a bit of a leap of logic for me. – user176049 Sep 27 '14 at 21:53
• The last sum is $\sum_{k=2}^n\cdots\cdots$. Suppose $\ell=k-2$, so that $\ell$ goes from $0$ to $n-2$. Then the sum is $\displaystyle\sum_{\ell=0}^{n-2} \binom{n-2}\ell$, so it's the total number of subsets of a size-$(n-2)$ set; thus it is $2^{n-2}$. ${}\qquad{}$ – Michael Hardy Sep 27 '14 at 21:57
• Ah, thank you. That makes this explanation clear from an algebraic stance. – user176049 Sep 27 '14 at 21:59