Question

For any positive integers m, n (with $n\ge m$), let $\left( \begin{matrix} n \\\ m \\\ \end{matrix} \right)={}^{n}{{C}_{m}}$. Prove that $\left( \begin{matrix} n \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-1 \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-2 \\\ m \\\ \end{matrix} \right)+......+\left( \begin{matrix} m \\\ m \\\ \end{matrix} \right)=\left( \begin{matrix} n+1 \\\ m+1 \\\ \end{matrix} \right)$?

Answer 1

We start solving the problem by assuming the value of L.H.S as x. We then use the property that for any positive integer ‘a’, we have ${}^{a}{{C}_{a}}=1$ for ${}^{m}{{C}_{m}}$ and replace it with ${}^{m+1}{{C}_{m+1}}$. We then use the property ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ for next consecutive terms from the right to left continuously. After applying the property ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ to all the terms present in the L.H.S (Left Hand Side), we get the required result.

Complete step-by-step solution

According to the problem, it is given that $\left( \begin{aligned} & n \\\ & m \\\ \end{aligned} \right)={}^{n}{{C}_{m}}$ for any positive integers m, n (with $n\ge m$). We need to prove $\left( \begin{matrix} n \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-1 \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-2 \\\ m \\\ \end{matrix} \right)+......+\left( \begin{matrix} m \\\ m \\\ \end{matrix} \right)=\left( \begin{matrix} n+1 \\\ m+1 \\\ \end{matrix} \right)$.
Let us consider L.H.S (Left Hand Side) and try to prove that it is equal to R.H.S (Right Hand Side).
Let us assume $x=\left( \begin{matrix} n \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-1 \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-2 \\\ m \\\ \end{matrix} \right)+......+\left( \begin{matrix} m \\\ m \\\ \end{matrix} \right)=\left( \begin{matrix} n+1 \\\ m+1 \\\ \end{matrix} \right)$.
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-2}{{C}_{m}}+......+{}^{m+2}{{C}_{m}}+{}^{m+1}{{C}_{m}}+{}^{m}{{C}_{m}}$ ---(1).
We know that for any positive integer ‘a’, we have ${}^{a}{{C}_{a}}=1$. Using this property, we get ${}^{m}{{C}_{m}}={}^{m+1}{{C}_{m+1}}=1$. Let us use this result in equation (1).
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-2}{{C}_{m}}+......+{}^{m+2}{{C}_{m}}+{}^{m+1}{{C}_{m}}+1$ ---(2).
Let us replace ‘1’ with ${}^{m+1}{{C}_{m+1}}$ in equation (2) as we have ${}^{m+1}{{C}_{m+1}}=1$.
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-2}{{C}_{m}}+......+{}^{m+2}{{C}_{m}}+{}^{m+1}{{C}_{m}}+{}^{m+1}{{C}_{m+1}}$ ---(3).
We know that ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$. Let us use this result in equation (3).
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-2}{{C}_{m}}+......+{}^{m+2}{{C}_{m}}+{}^{m+2}{{C}_{m+1}}$.
Let us use the result ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ again.
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-2}{{C}_{m}}+......+{}^{m+2}{{C}_{m+1}}$.
This trend continues up to ${}^{n-2}{{C}_{m}}$ y using the property ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$which makes the sum of remaining terms is equal to ${}^{n-2}{{C}_{m+1}}$.
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-2}{{C}_{m}}+{}^{n-2}{{C}_{m+1}}$.
Let us use the result ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ again.
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-1}{{C}_{m+1}}$.
Let us use the result ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ again.
$\Rightarrow x={}^{n}{{C}_{m}}+{}^{n}{{C}_{m+1}}$.
Let us use the result ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ again.
$\Rightarrow x={}^{n+1}{{C}_{m+1}}$.
So, we have found that ${}^{n}{{C}_{m}}+{}^{n-1}{{C}_{m}}+{}^{n-2}{{C}_{m}}+......+{}^{m+2}{{C}_{m}}+{}^{m+1}{{C}_{m}}+{}^{m}{{C}_{m}}={}^{n+1}{{C}_{m+1}}$.
This tells us that we have proved $\left( \begin{matrix} n \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-1 \\\ m \\\ \end{matrix} \right)+\left( \begin{matrix} n-2 \\\ m \\\ \end{matrix} \right)+......+\left( \begin{matrix} m \\\ m \\\ \end{matrix} \right)=\left( \begin{matrix} n+1 \\\ m+1 \\\ \end{matrix} \right)$.

Note: We should not assume ${}^{n+1}{{C}_{r}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ as it is wrong and is the most common mistake many people commit. We should know that in a combination ${}^{a}{{C}_{b}}$, ‘a’ and ‘b’ must be a whole number and $a\ge b$ otherwise, the given problem is wrong. Whenever we get this type of problems, we try to make use of the property ${}^{n}{{C}_{r+1}}+{}^{n}{{C}_{r}}={}^{n+1}{{C}_{r+1}}$ at the required places. If we are given the absolute integer values for ‘m’ and ‘n’, we could have got the result in an integer.