Solveeit Logo
Login

Question

Question: Show that \(^n{C_r}{ = ^{n - 1}}{C_r}{ + ^{n - 1}}{C_{r - 1}}\)...

Show that nCr=n−1Cr+n−1Cr−1^n{C_r}{ = ^{n - 1}}{C_r}{ + ^{n - 1}}{C_{r - 1}}

Explanation

Solution

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 nCr^n{C_r} directly here to prove the above. The general formula to be used in the entire process will be as follows
nCr=n!r!(n−r)!^n{C_r} = \dfrac{{n!}}{{r!\left( {n - r} \right)!}}
First we will start with the Right hand side.
R.H.S = n−1Cr+n−1Cr−1^{n - 1}{C_r}{ + ^{n - 1}}{C_{r - 1}}
=(n−1)!r!(n−1−r)!+(n−1)!(r−1)!(n−1−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)!}}
=(n−1)!r!(n−1−r)!+(n−1)!(r−1)!(n−r)!= \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(p−1)!p! = p\left( {p - 1} \right)! is the property of factorial which we can use in the first term
R.H.S =(n−1)!r(r−1)!(n−1−r)!+(n−1)!(r−1)!(n−r)! = \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=(n−1)!r(r−1)!(n−1−r)!+(n−1)!(r−1)!(n−r)(n−r−1)! = \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 =(n−1)!(r−1)!(n−r−1)!(1r+1n−r) = \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 =(n−1)!(r−1)!(n−r−1)!(n−r+rr(n−r)) = \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)
=(n−1)!(r−1)!(n−r−1)!.nr(n−r)= \dfrac{{\left( {n - 1} \right)!}}{{\left( {r - 1} \right)!\left( {n - r - 1} \right)!}}.\dfrac{n}{{r\left( {n - r} \right)}}
=n(n−1)!r(r−1)!(n−r)(n−r−1)!= \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=n!r!(n−r)!\dfrac{{n!}}{{r!\left( {n - r} \right)!}} = nCr^n{C_r}= L.H.S
Hence we have proved that nCr=n−1Cr+n−1Cr−1^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.