3
$\begingroup$

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.

Thanks in advance for your help.

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.