Animated Solution for Mathematics - Binomial Theorem: Using mathematical induction, prove that ${}^m{C}_0^n{C}_k{+}^m{C}_1^n{C}_{k-1}+....{+}^m{C}_k^n{C}_0{=}^{(m+n)}{C}_k$, where $m,n,k$ are positive integers, and ${}^p{C}_q=0$ for $p<q$.

Welcome, future engineer. Today, we are not just solving an equation; we are uncovering a fundamental truth about how we count.

We are looking at Vandermonde's Identity:

At first glance, this might look like a daunting summation, but I want you to pause and visualize the story behind it. Imagine you are standing in front of two distinct groups of objects: one group has $m$ items, and the other has $n$ items.

You are tasked with selecting a total of $k$ items from this combined collection of $m+n$ items. You could pick $r$ items from the first group and $k-r$ items from the second. If you sum all these possibilities across every valid value of $r$, you get the total ways to choose $k$ items from $m+n$.

That is the intuition. Now, let us prove it with the rigor of mathematical induction.

Defining $P(m)$

To begin our journey, we define our proposition $P(m)$ as the identity itself. We are treating $n$ and $k$ as fixed constants, and we are going to prove that this holds for all positive integers $m$.

Our base case is $m=1$. When we substitute $m=1$ into our left-hand side, we get:

Remember, ${}^1{C}_r$ is zero for any $r>1$. This means our summation collapses instantly, leaving only the terms for $r=0$ and $r=1$.

We are left with:

Does this look familiar? It is the classic Pascal's Identity! The sum of these two terms is exactly ${}^{n+1}{C}_k$. Since our right-hand side for $m=1$ is ${}^{1+n}{C}_k$, our base case is rock solid.

Now, we assume $P(m)$ is true. This is our Inductive Hypothesis. We accept that the following is a fact:

Our goal is to prove $P(m+1)$, which means showing that the sum for $m+1$ equals ${}^{m+n+1}{C}_k$. Let us write the left-hand side for $m+1$:

Here is where the magic happens. We apply Pascal's Identity to the term ${}^{m+1}{C}_r$, breaking it into ${}^m{C}_r+{}^m{C}_{r-1}$. Substituting this into our sum, we get:

Distributing the terms, we can split this into two separate summations, $S_1$ and $S_2$:

Look at $S_1$. It is identical to our Inductive Hypothesis! We can immediately replace it with ${}^{m+n}{C}_k$.

Now, look at $S_2$. It looks slightly different because of the $r-1$ index. Let us perform a substitution: let $j=r-1$.

As $r$ goes from $0$ to $k$, $j$ goes from $-1$ to $k-1$. Since ${}^m{C}_{-1}=0$, we can ignore the $j=-1$ term and start our sum from $j=0$. The expression becomes:

Notice what we have achieved. $S_2$ is now in the exact form of our original identity, but with $k$ replaced by $k-1$. Therefore, $S_2={}^{m+n}{C}_{k-1}$.

Now, we combine our results:

Applying Pascal's Identity one final time, we get ${}^{m+n+1}{C}_k$. This is exactly the right-hand side of $P(m+1)$.

We have successfully bridged the gap. By the Principle of Mathematical Induction, Vandermonde's Identity is proven for all positive integers $m$. You have just navigated one of the most beautiful proofs in combinatorics.