Algebric proof for the identity $n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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