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?
 A: 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}$$
