# Combinatorial proof of $n(n-1)2^{n-2} = \sum_{i=2}^{n}k(k-1)\binom{n}{k}$

Today I had a combinatronics test, and I really couldn't do this problem, it said to give a combinatorial proof of:

$$n(n-1)2^{n-2} = \sum_{i=2}^{n}k(k-1)\binom{n}{k}$$

It said that it should be derived from the binomial theorem. But I am not able to see it. I thought about using the identity $$2^{n} = \sum_{i=0}^{n}\binom{n}{k}$$ Also I thought about using the fact that:
$$1 +2+ 3+ \cdots + n = \frac{n(n+1)}{2}$$

But I didn't get anywhere. It MUST be a combinatorial proof.

• This answer contains a hint. (Other answers to that question give other kinds of proofs.) – Brian M. Scott Feb 10 '15 at 22:26

Think about a set of $n$ elements, and you want to pick a special marked subset as follows: pick two distinguished (and taking order into account) elements from the set, and then the rest of the subset is arbitrary unordered elements. Clearly this is $n(n-1)2^{n-2}$ ways. However, if you consider breaking up the calculation according to different subset sizes $k$, then you get your summation formula. So the two quantities are equal.

Let $$f(x)=(x+1)^n$$ $$f(x)=(x+1)^n=\sum_{k=0}^{n}x^k\binom{n}{k}$$

$$f''(x)=n(n-1)(x+1)^{n-2}=\sum_{k=2}^{n}k(k-1)x^{k-2}\binom{n}{k}$$ $$f''(1)=n(n-1)2^{n-2}=\sum_{k=2}^{n}k(k-1)\binom{n}{k}$$