Solveeit Logo
Login

Question

Question: Prove the following: \[^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}={{\text{ }}^{n+1}}{{C}_{r}}\]...

Prove the following: nCr+ nCr−1= n+1Cr^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}={{\text{ }}^{n+1}}{{C}_{r}}

Explanation

Solution

To solve this question, we will first consider LHS of the above equation then we will use the formula of nCr^{n}{{C}_{r}} which is given as nCr=n!r!(n−r)!^{n}{{C}_{r}}=\dfrac{n!}{r!\left( n-r \right)!} where n! is n factorial. Finally, splitting the LHS using this formula, we will solve to get the RHS.

Complete step by step answer:
Let us first define nCr^{n}{{C}_{r}} and nPr.^{n}{{P}_{r}}. nPr^{n}{{P}_{r}} is defined as the number of possibilities for choosing an ordered set of r objects (a permutation) from the total of n objectives and nCr^{n}{{C}_{r}} is defined as the number of different unordered combinations of r objects from a set of n objects.
nCr=n!r!(n−r)!^{n}{{C}_{r}}=\dfrac{n!}{r!\left( n-r \right)!}
nPr=n!(n−r)!^{n}{{P}_{r}}=\dfrac{n!}{\left( n-r \right)!}
To show that nCr+ nCr−1= n+1Cr^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}={{\text{ }}^{n+1}}{{C}_{r}} we will consider the LHS first.
nCr+ nCr−1^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}
Splitting using the above stated formula of combination, we have,
⇒nCr+ nCr−1=n!(n−r)!r!+n!(n−r+1)!(r−1)!{{\Rightarrow }^{n}}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}=\dfrac{n!}{\left( n-r \right)!r!}+\dfrac{n!}{\left( n-r+1 \right)!\left( r-1 \right)!}
Taking n! common, we have,
⇒n![1(n−r)!r!+1(n−r+1)!(r−1)!]\Rightarrow n!\left[ \dfrac{1}{\left( n-r \right)!r!}+\dfrac{1}{\left( n-r+1 \right)!\left( r-1 \right)!} \right]
Splitting r! as r(r – 1)! In the denominator of the first term, we have,
⇒n![1(n−r)!r(r−1)!+1(n−r+1)!(r−1)!]\Rightarrow n!\left[ \dfrac{1}{\left( n-r \right)!r\left( r-1 \right)!}+\dfrac{1}{\left( n-r+1 \right)!\left( r-1 \right)!} \right]
Now, let us take (r – 1)! common from the denominator. Doing so, we have,
⇒n!(r−1)![1(n−r)!r+1(n−r+1)!]\Rightarrow \dfrac{n!}{\left( r-1 \right)!}\left[ \dfrac{1}{\left( n-r \right)!r}+\dfrac{1}{\left( n-r+1 \right)!} \right]
Now splitting (n – r + 1)! In the denominator of the second term of the above obtained equation, we have,
⇒n!(r−1)![1r(n−r)!+1(n−r+1)(n−r)!]\Rightarrow \dfrac{n!}{\left( r-1 \right)!}\left[ \dfrac{1}{r\left( n-r \right)!}+\dfrac{1}{\left( n-r+1 \right)\left( n-r \right)!} \right]
Let us take (n – r)! common from the denominator, we have,
⇒n!(r−1)!(n−r)![1r+1(n−r+1)]\Rightarrow \dfrac{n!}{\left( r-1 \right)!\left( n-r \right)!}\left[ \dfrac{1}{r}+\dfrac{1}{\left( n-r+1 \right)} \right]
Let us take the LCM and solve further the question we have.
⇒n!(r−1)!(n−r)![(n−r+1)+rr(n−r+1)]\Rightarrow \dfrac{n!}{\left( r-1 \right)!\left( n-r \right)!}\left[ \dfrac{\left( n-r+1 \right)+r}{r\left( n-r+1 \right)} \right]
⇒n!(r−1)!(n−r)![n−r+1+rr(n−r+1)]\Rightarrow \dfrac{n!}{\left( r-1 \right)!\left( n-r \right)!}\left[ \dfrac{n-r+1+r}{r\left( n-r+1 \right)} \right]
⇒n!(r−1)!(n−r)![n+1r(n−r+1)]\Rightarrow \dfrac{n!}{\left( r-1 \right)!\left( n-r \right)!}\left[ \dfrac{n+1}{r\left( n-r+1 \right)} \right]
Opening the bracket and using n!(n + 1) = (n + 1)!, we have,
⇒n!(r−1)!(n−r)!n+1r(n−r+1)\Rightarrow \dfrac{n!}{\left( r-1 \right)!\left( n-r \right)!}\dfrac{n+1}{r\left( n-r+1 \right)}
⇒n!(n+1)(n−r+1)(r−1)!r(n−r)!\Rightarrow \dfrac{n!\left( n+1 \right)}{\left( n-r+1 \right)\left( r-1 \right)!r\left( n-r \right)!}
⇒(n+1)!(n−r+1)(r−1)!r(n−r)!\Rightarrow \dfrac{\left( n+1 \right)!}{\left( n-r+1 \right)\left( r-1 \right)!r\left( n-r \right)!}
Using r(r – 1)! = r! and (n – r + 1)(n – r)! = (n – r + 1)!, we have,
nCr+ nCr−1⇒(n+1)!r!(n−r+1)!^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}\Rightarrow \dfrac{\left( n+1 \right)!}{r!\left( n-r+1 \right)!}
Which is nothing but (n+1)!r!(n−r+1)!= n+1Cr.\dfrac{\left( n+1 \right)!}{r!\left( n-r+1 \right)!}={{\text{ }}^{n+1}}{{C}_{r}}.
Hence, nCr+ nCr−1= n+1Cr^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}={{\text{ }}^{n+1}}{{C}_{r}}
Hence proved.

Note: The possibility of mistake can be opening all the factorial and solving n!=n(n−1)(n−2)....2.1.n!=n\left( n-1 \right)\left( n-2 \right)....2.1. This opening is not necessary because we anyways need n+1Cr^{n+1}{{C}_{r}} at the end. So, we need factorial (n + 1)! and r! at the end. Hence, opening the factorial would lead to confusion. Therefore, avoid doing that.