Prove $\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$

Question

Prove $$\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$$

Proof by induction: true for $n=2$. Assume true for $n$ and see if $n+1$ is true.

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

Then

$$\sum _{k=2}^{n+1} k(k-1) {n+1 \choose k}=\sum _{k=2}^{n+1} k(k-1) ({n \choose k-1}+{n\choose k})$$

From here I can separate the summ into 2:

$$\sum _{k=2}^{n+1} k(k-1) {n \choose k-1}+\sum _{k=2}^{n+1} k(k-1) {n \choose k}$$, where the latter is simply $n(n-1)2^{n-2}$ by the induction hypothesis. I assumed ${n\choose n+1}=0$.

However, I'm not sure what to do with $$\sum _{k=2}^{n+1} k(k-1){n \choose k-1}$$

Answer 1

Consider the classical binomial identity under the form

$$\sum _{k=0}^{n} {n \choose k}x^k=(1+x)^{n}$$

derivate twice, then replace $x$ by 1.

Answer 2

I'm not sure how to proceed with your induction proof.

A more direct approach is to write:

$$\begin{align}k(k-1)\binom{n}{k}&=k(k-1)\frac{n!}{k!(n-k)!}\\ &=n(n-1)\frac{(n-2)!}{(k-2)!(n-k)!}\\ &=n(n-1)\binom{n-2}{k-2} \end{align}$$

Answer 3

$$\sum_{k=2}^{n}k\left(k-1\right)\binom{n}{k}=\sum_{k=2}^{n}\frac{n!}{\left(k-2\right)!\left(n-k\right)!}=n\left(n-1\right)\sum_{k=2}^{n}\binom{n-2}{k-2}=\cdots$$

Answer 4

Suppose that you want to choose a committee from $n$ people so that this committee has a president and a vice-president. The smallest committee here would have just a president and a vice-president (two members).

One way to find the number of ways to do this is to sort by committee size and sum them up (as they are disjoint).$$\sum_{k=2}^nk(k-1)\binom{n}k$$The summand represents the number of ways to select the committee of size $k$, along with choosing the two officials.

Another way to find the number of ways is to do this: among the original sample of people, start by choosing a president and a vice-president. These two tasks can be done in $n\cdot(n-1)$ ways. Now, for each of the rest ($n-2$ people) we either include them in the committee, or we don't - that is two choices for $n-2$ people, each independent of the other. Our grand total should become:$$n(n-1)\cdot \underbrace{2\cdot 2 \cdots 2}_{n-2 ~\text{times}} = n(n-1)2^{n-2} $$which is identical to the right-hand-side.

Answer 5

Recall $$f_n (z) = \sum_{k=0}^n \binom{n}{k} z^k = (1+z)^n,$$ by the binomial theorem. Now observe for $0 \le m \le k \le n$, $$\begin{align*} \binom{k}{m}\binom{n}{k} &= \frac{k!}{m! \, (k-m)!} \cdot \frac{n!}{k! \, (n-k)!} \\ &= \frac{n!}{m! \, (k-m)! \, (n-k)!} \\ &= \frac{n!}{m! \, (n-m)!} \cdot \frac{(n-m)!}{(k-m)! \, (n-k)!} \\ &= \binom{n}{m} \binom{n-m}{k-m}. \end{align*}$$ So consider $$g_{n,m}(z) = \sum_{k=m}^n \binom{k}{m}\binom{n}{k} z^k = \binom{n}{m} \sum_{k=m}^n \binom{n-m}{k-m} z^k,$$ where $\binom{n}{m}$ factors out, being independent of the index of summation $k$. Next, letting $j = k-m$, we find $$\begin{align*} g_{n,m}(z) &= \binom{n}{m} \sum_{j=0}^{n-m} \binom{n-m}{j} z^{j+m} \\ &= \binom{n}{m} z^m \sum_{j=0}^{n-m} \binom{n-m}{j} z^j \\ &= \binom{n}{m} z^m f_{n-m}(z) \\ &= \binom{n}{m} z^m (1+z)^{n-m}. \end{align*}$$ This result generalizes the given sum, since $k(k-1) = 2\binom{k}{2}$; that is to say, the given sum is the special case $$2g_{n,2}(1) = 2 \binom{n}{2} 1^2 (1+1)^{n-2} = n(n-1) 2^{n-2}.$$