Question

Show that $^n{C_r}{ = ^{n - 1}}{C_r}{ + ^{n - 1}}{C_{r - 1}}$

Answer 1

Hint: The only way to go ahead with this problem is to start applying the formula of the combinations and proceed. Since the formula contains factorial you can use the factorial properties as needed to simplify the equation. The process also involves back and forth rearrangements of terms.

Complete step by step answer:
We directly have to use the formula of $^n{C_r}$ directly here to prove the above. The general formula to be used in the entire process will be as follows
$^n{C_r} = \dfrac{{n!}}{{r!\left( {n - r} \right)!}}$
First we will start with the Right hand side.
R.H.S = $^{n - 1}{C_r}{ + ^{n - 1}}{C_{r - 1}}$
$ = \dfrac{{\left( {n - 1} \right)!}}{{r!\left( {n - 1 - r} \right)!}} + \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - 1 - r + 1} \right)!}}$
$ = \dfrac{{\left( {n - 1} \right)!}}{{r!\left( {n - 1 - r} \right)!}} + \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - r} \right)!}}$
Now we know that $p! = p\left( {p - 1} \right)!$ is the property of factorial which we can use in the first term
R.H.S $ = \dfrac{{\left( {n - 1} \right)!}}{{r\left( {r - 1} \right)!\left( {n - 1 - r} \right)!}} + \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - r} \right)!}}$
Again applying the factorial property for second term we get
R.H.S$ = \dfrac{{\left( {n - 1} \right)!}}{{r\left( {r - 1} \right)!\left( {n - 1 - r} \right)!}} + \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - r} \right)\left( {n - r - 1} \right)!}}$
Taking out the common terms we get
R.H.S $ = \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - r - 1} \right)!}}\left( {\dfrac{1}{r} + \dfrac{1}{{n - r}}} \right)$
Solving the bracket we get
R.H.S $ = \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - r - 1} \right)!}}\left( {\dfrac{{n - r + r}}{{r\left( {n - r} \right)}}} \right)$
$ = \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - r - 1} \right)!}}.\dfrac{n}{{r\left( {n - r} \right)}}$
$ = \dfrac{{n\left( {n - 1} \right)!}}{{r\left( {r - 1} \right)!\left( {n - r} \right)\left( {n - r - 1} \right)!}}$
Using the same property of factorial above we get
R.H.S=$\dfrac{{n!}}{{r!\left( {n - r} \right)!}}$ = $^n{C_r}$= L.H.S
Hence we have proved that $^n{C_r}{ = ^{n - 1}}{C_r}{ + ^{n - 1}}{C_{r - 1}}$

Note: The above proof is one of the standard results of combination. This results are used as properties when solving examples related to combinations. This results are also used in solving sums from different fields which involves combination as their main concept such as in binomial distribution.