# Combinatorial Proofs for Simple Binomial Identities

Consider $\sum k(k-1)(k-2)$ $n\choose k$ = $n(n-1)(n-2)$ $n-3 \choose 3$ for k >= 0 n >=3

I had initially thought the right side counted the ways to select three distinct objects from n and then choose an additional three arbitrarily from the remaining objects but I was unsure on how the LHS summation fit into the picture. Does it make sense to choose distinguished objects for all k? I feel like there is another identity that ties into this, where the sum $\sum$ $n \choose k$ over all k is just the same as choosing from the largest element. Does anyone recall whether something like that exists?

• The RHS should be $2^{n-3}n(n-1)(n-2)$. – user17762 Apr 21 '13 at 0:26
• Unfortunately this book disagrees with you. – 114 Apr 21 '13 at 0:27
• Then it is incorrect. – user17762 Apr 21 '13 at 0:28
• Is it possible that there are two such identities that happen to be very similar? – 114 Apr 21 '13 at 0:29
• @user17762 You probably mean that $2^{n-3}$ should replace the binomial coefficient on the RHS. The other factors $n(n-1)(n-2)$ should stay as they are. – Andreas Blass Apr 21 '13 at 0:29

I assume the right hand side is $2^{n-3}$ instead of $\dbinom{n}3$. Say we want to form a baseball team from $n$ people. There can be any number of people in the team. However, the team must have a captain, vice-captain and a cheer leader (The cheer leader can be of any gender and is also a part of the team). Then there are two ways to do this.

First method

First choose a captain: this can be done in $n$ ways. Next choose the vice-captain: this can be done in $n-1$ ways. Then, choose the cheer leader: this can be done in $n-2$ ways. The rest of the team from the remaining $n-3$ people can be formed in $2^{n-3}$ ways. Hence, the total number of ways is $n(n-1)(n-2) \cdot 2^{n-3}$ ways.

Second method

First choose a team with $k$ people. Now the captain can be selected in $k$ ways, the vice-captain can be selected in $k-1$ ways and the cheer leader can be selected in $k-2$ ways. Hence, the total number of ways of forming a team with $k$ people is $$\dbinom{n}k k(k-1)(k-2)$$ Now sum this over $k$ from $3$ to $n$ to get all possible teams.

Since both the methods count the same thing, they need to be equal and hence $$\sum_k \dbinom{n}k k(k-1)(k-2) = n(n-1)(n-2) \cdot 2^{n-3}$$

• That does make perfect sense when $2^{n-3}$ replaces $n-3 \choose k$, thanks! – 114 Apr 21 '13 at 0:36