3
$\begingroup$

Prove the identity:

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

I tried using the binomial coefficients identity $2^n = \sum_{k=1}^n {n \choose k}$ but got stuck along the way.

$\endgroup$
  • $\begingroup$ If you don't write anything inside the summation, this makes no sense. $\endgroup$ – Crostul Nov 9 '14 at 11:21
  • $\begingroup$ Sorry guys, fixed the typo. $\endgroup$ – AlonAlon Nov 9 '14 at 11:23
  • $\begingroup$ Do you insist on an algebraic proof? A combinatorial one is very easy. $\endgroup$ – Brian M. Scott Nov 9 '14 at 11:24
  • $\begingroup$ @BrianM.Scott, I don't have to use an algebric proof actually $\endgroup$ – AlonAlon Nov 9 '14 at 11:32
4
$\begingroup$

HINT:

For $k\ge2,$

$$k(k-1)\binom nk=k(k-1)n(n-1)\frac{(n-2)!}{k(k-1)\cdot (k-2)! \{(n-2)-(k-2)\}!}$$

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

$\endgroup$
4
$\begingroup$

The $n(n-1)$ and $k(k-1)$ are a signal that differentiating twice should be at hand.

So start with $$ (1+X)^n=\sum_k\binom nkX^k, $$ differentiate twice with respect to $X$ to get$$ n(n-1)(1+X)^{n-2}=\sum_k\binom nk k(k-1)X^k, $$ and finally set $X:=1$.

$\endgroup$
3
$\begingroup$

HINT: Start with a pool of $n$ people. You want to pick a team of at least two people, designate one member of the team as captain, and designate a different member of the team as assistant captain. Both sides count the ways to do this. More details in the spoiler-protected block if you get stuck.

On the left you’re picking the captain and assistant captain and the rest of the team. On the right you’re choosing the team size, $k$, picking the team, and then choosing a captain and assistant captain from that team.

$\endgroup$
3
$\begingroup$

We can make use of the following binomial identity: $$\binom ab\binom bc=\binom ac \binom {a-c}{b-c}$$ Also, we can take the summation from $k=2$ instead of $k=1$, since the latter yields a zero term.

Hence $$\begin{align} \sum_{k=1}^n k(k-1)\binom nk&=\sum_{k=2}^n \binom nk k(k-1)\\ &=2\sum_{k=2}^n \binom nk\binom k2\\ &=2\sum_{k=2}^n \binom n2 {n-2\choose k-2}\\ &=2\binom n2 \sum_{k=2}^n {n-2\choose k-2}\\ &=n(n-1)\sum_{k=0}^{n-2} {n-2\choose k}\\ &=n(n-1)2^{n-2}\qquad \blacksquare \end{align}$$


An interesting point to note:

From the above result, by dividing both sides by 2 and noting that $\frac{r(r-1)}2=\binom r2$we can see that $$\sum_{k=2}^n \binom k2 \binom nk=\binom n22^{n-2}$$

This forms a nice pattern continuing from the commonly known results: $$\sum_{k=1}^n \binom k1 \binom nk=\binom n1 2^{n-1}$$ and $$\sum_{k=0}^n \binom k0 \binom nk=\binom n0 2^{n-0}$$

NB: the last two are equations in their more commonly known forms are
$\sum_{k=1}^n k\binom nk=n\cdot 2^{n-1}$ and $\sum_{k=0}^n \binom nk=2^n$ respectively.

From the pattern it appears that $$\sum_{k=m}^n \binom km \binom nk =\binom nm 2^{n-m}$$

This can easily be proven as follows: $$\begin{align} \sum_{k=m}^n \binom km \binom nk &=\sum_{k=m}^n \binom nk \binom km \\ &=\sum_{k=m}^n \binom nm \binom {n-m}{k-m}\\ &=\binom nm\sum_{k=m}^n \binom {n-m}{k-m}\\ &=\binom nm\sum_{k=0}^{n-m} \binom {n-m}{k}\\ &=\binom nm 2^{n-m} \end{align}$$

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