Question

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

Answer 1

Hint: To solve this question, we will first consider LHS of the above equation then we will use the formula of \[^{n}{{C}_{r}}\] which is given as \[^{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 \[^{n}{{C}_{r}}\] and \[^{n}{{P}_{r}}.\] \[^{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 \[^{n}{{C}_{r}}\] is defined as the number of different unordered combinations of r objects from a set of n objects.
\[^{n}{{C}_{r}}=\dfrac{n!}{r!\left( n-r \right)!}\]
\[^{n}{{P}_{r}}=\dfrac{n!}{\left( n-r \right)!}\]
To show that \[^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}={{\text{ }}^{n+1}}{{C}_{r}}\] we will consider the LHS first.
\[^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}\]
Splitting using the above stated formula of combination, we have,
\[{{\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,
\[\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,
\[\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,
\[\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,
\[\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,
\[\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.
\[\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]\]
\[\Rightarrow \dfrac{n!}{\left( r-1 \right)!\left( n-r \right)!}\left[ \dfrac{n-r+1+r}{r\left( n-r+1 \right)} \right]\]
\[\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,
\[\Rightarrow \dfrac{n!}{\left( r-1 \right)!\left( n-r \right)!}\dfrac{n+1}{r\left( n-r+1 \right)}\]
\[\Rightarrow \dfrac{n!\left( n+1 \right)}{\left( n-r+1 \right)\left( r-1 \right)!r\left( n-r \right)!}\]
\[\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,
\[^{n}{{C}_{r}}+{{\text{ }}^{n}}{{C}_{r-1}}\Rightarrow \dfrac{\left( n+1 \right)!}{r!\left( n-r+1 \right)!}\]
Which is nothing but \[\dfrac{\left( n+1 \right)!}{r!\left( n-r+1 \right)!}={{\text{ }}^{n+1}}{{C}_{r}}.\]
Hence, \[^{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\left( n-1 \right)\left( n-2 \right)....2.1.\] This opening is not necessary because we anyways need \[^{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.