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

• No, you should use the formula for $\binom nk$ and see that LHS = RHS – user228113 Dec 16 '17 at 18:18
• meaning that you shall express ${n \choose m}$ as $n(n-1) \cdots (n-m+1)/m!$ – G Cab Dec 16 '17 at 18:21

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.

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

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.