Show that $\binom{n}{1} + 6\binom{n}{2} + 6\binom{n}{3} = n^3$ Sorry, I'm reviewing for an exam and I can't figure out this practice problem - I know I'm supposed to use some version of the Binomial Theorem but I can't figure out how to apply it.
How can we show 

$$\binom{n}{1} + 6\binom{n}{2} + 6\binom{n}{3} = n^3$$

 A: Can't you just work out the terms?
${n \choose 1 }=n$
${n \choose 2 }= \frac{n(n-1)}{2}$
${n \choose 3 }= \frac{n(n-1)(n-2)}{6}$
Fill in and work it out
A: You can prove this also by using a combinatorial argument. Say we have a $n$ letters and we want to make a words of length $3$ with those $n$ letters. This can be done of course on $n^3$ ways. On the other hand we can make:
words with no different letters and we have ${n\choose 1}$ of those;
words with 2 different letters and we have ${n\choose 2}$ pairs of those letters and we can with specific pair make 6 different words, so we have 6${n\choose 2}$ of those; 
words with 3 different letters and we have ${n\choose 3}$ triples of those letters and we can with specific triple make 6 different words, so we have 6${n\choose 3}$ of those. 
We are done.
A: Note that
$$
\binom{n}{1} + 6\binom{n}{2} + 6\binom{n}{3}-n^3
$$
is a polynomial of degree at most $3$ in $n$ which has roots at $n=1,2,3,4$. Since this polynomial has at least four roots it is identically the zero polynomial and the result follows.
