2
$\begingroup$

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

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

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.