Verifying the Binomial Formula with Mathematical Induction

The binomial formula states:

$$(z_1 + z_2)^n = \sum_{k=0}^n \binom{n}{k} z_1^{n-k} z_2^k$$

where $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ and $n = 1, 2, \ldots$. This is a powerful formula in algebra, expressing the expansion of $(z_1 + z_2)^n$ as a sum of terms involving powers of $z_1$ and $z_2$.

We’ll verify this formula using mathematical induction. Mathematical induction is a logical method to prove that a statement holds for all positive integers $n$. The process involves two steps:

1. Base Case: Verify the formula for the smallest value of $n$, typically $n = 1$.
2. Inductive Step: Assume the formula holds for some $n = k$, and then prove it holds for $n = k+1$.

---

Step 1: Base Case ($n = 1$)

For $n = 1$, the formula becomes:

$$(z_1 + z_2)^1 = \sum_{k=0}^1 \binom{1}{k} z_1^{1-k} z_2^k$$

Let’s calculate both sides:

• Left-hand side:

$$(z_1 + z_2)^1 = z_1 + z_2$$

• Right-hand side:

$$\sum_{k=0}^1 \binom{1}{k} z_1^{1-k} z_2^k = \binom{1}{0} z_1^1 z_2^0 + \binom{1}{1} z_1^0 z_2^1$$

Here, $\binom{1}{0} = 1$ and $\binom{1}{1} = 1$, so:

$$\sum_{k=0}^1 \binom{1}{k} z_1^{1-k} z_2^k = 1 \cdot z_1 + 1 \cdot z_2 = z_1 + z_2$$

Since both sides are equal, the base case holds.

---

Step 2: Inductive Step

Assume the formula is true for $n = k$, i.e.,

$$(z_1 + z_2)^k = \sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^j$$

This is called the inductive hypothesis. We need to prove it holds for $n = k+1$, i.e.,

$$(z_1 + z_2)^{k+1} = \sum_{j=0}^{k+1} \binom{k+1}{j} z_1^{k+1-j} z_2^j$$

Expanding $(z_1 + z_2)^{k+1}$:

Using the distributive property of multiplication:

$$(z_1 + z_2)^{k+1} = (z_1 + z_2) \cdot (z_1 + z_2)^k$$

Substitute the inductive hypothesis for $(z_1 + z_2)^k$:

$$(z_1 + z_2)^{k+1} = (z_1 + z_2) \cdot \sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^j$$

Distribute $z_1 + z_2$ across the summation:

$$(z_1 + z_2)^{k+1} = \sum_{j=0}^k \binom{k}{j} z_1^{k-j+1} z_2^j + \sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^{j+1}$$

Combining the Two Sums:

Reindex the second summation by letting $i = j+1$ (so $j = i-1$):

$$\sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^{j+1} = \sum_{i=1}^{k+1} \binom{k}{i-1} z_1^{k+1-i} z_2^i$$

Now the total expression becomes:

$$(z_1 + z_2)^{k+1} = \sum_{j=0}^k \binom{k}{j} z_1^{k-j+1} z_2^j + \sum_{i=1}^{k+1} \binom{k}{i-1} z_1^{k+1-i} z_2^i$$

Merge these two sums by observing they overlap for $j = i-1$:

$$(z_1 + z_2)^{k+1} = \sum_{i=0}^{k+1} \left[\binom{k}{i} + \binom{k}{i-1}\right] z_1^{k+1-i} z_2^i$$

Applying the Binomial Coefficient Identity:

The identity $\binom{k+1}{i} = \binom{k}{i} + \binom{k}{i-1}$ allows us to simplify:

$$(z_1 + z_2)^{k+1} = \sum_{i=0}^{k+1} \binom{k+1}{i} z_1^{k+1-i} z_2^i$$

This matches the binomial formula for $n = k+1$. Thus, the inductive step is complete.

---

Conclusion

By proving the base case and the inductive step, we’ve shown that the binomial formula:

$$(z_1 + z_2)^n = \sum_{k=0}^n \binom{n}{k} z_1^{n-k} z_2^k$$

is true for all positive integers $n$. This concludes the proof!

PS

Reindexing the Sum and Binomial Coefficients: A Detailed Breakdown

Reindexing a summation is often a tricky step in proofs, especially when working with summations involving binomial coefficients. Below, I’ll explain the reindexing step from the proof of the binomial formula in much greater detail, using simple examples and visual aids to show why it works.

---

Recap of the Key Step

From the inductive step of the proof:

$$(z_1 + z_2)^{k+1} = \sum_{j=0}^k \binom{k}{j} z_1^{k-j+1} z_2^j + \sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^{j+1}$$

The goal is to combine these two sums into one sum by reindexing the second summation.

Reindexing the Second Summation

In the second sum:

$$\sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^{j+1}$$

We let $i = j+1$. This substitution shifts the index $j$ to $i$, so that:

• When $j = 0$, $i = 1$,
• When $j = k$, $i = k+1$.

Thus, the summation becomes:

$$\sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^{j+1} = \sum_{i=1}^{k+1} \binom{k}{i-1} z_1^{k+1-i} z_2^i$$

Notice the changes:

1. The lower limit of the sum changes from $j = 0$ to $i = 1$.
2. The upper limit changes from $j = k$ to $i = k+1$.
3. The binomial coefficient $\binom{k}{j}$ is replaced with $\binom{k}{i-1}$, since $j = i-1$.
4. The powers of $z_1$ and $z_2$ are updated accordingly: $z_1^{k-j}$ becomes $z_1^{k+1-i}$, and $z_2^{j+1}$ becomes $z_2^i$.

---

Combining the Two Sums

Now the two summations can be written as:

1. $\sum_{j=0}^k \binom{k}{j} z_1^{k-j+1} z_2^j$,
2. $\sum_{i=1}^{k+1} \binom{k}{i-1} z_1^{k+1-i} z_2^i$.

We align their indices so both sums have the same variable (let’s use $i$):

• The first sum has $j = i$, so it remains: $$\sum_{i=0}^k \binom{k}{i} z_1^{k+1-i} z_2^i$$
• The second sum starts at $i = 1$ and ends at $i = k+1$: $$\sum_{i=1}^{k+1} \binom{k}{i-1} z_1^{k+1-i} z_2^i$$

The key observation is that both sums now share the same index $i$. Thus, they can be combined into a single summation:

$$(z_1 + z_2)^{k+1} = \sum_{i=0}^{k+1} \left[\binom{k}{i} + \binom{k}{i-1}\right] z_1^{k+1-i} z_2^i$$

---

Why This Works: The Binomial Coefficient Identity

The term $\binom{k}{i} + \binom{k}{i-1}$ is a fundamental identity of binomial coefficients. It states:

$$\binom{k+1}{i} = \binom{k}{i} + \binom{k}{i-1}$$

This identity comes from Pascal's triangle and reflects how each entry in the triangle is the sum of the two entries directly above it.

Here’s an example:

• If $k = 4$ and $i = 2$, $$\binom{4}{2} + \binom{4}{1} = \frac{4!}{2!(4-2)!} + \frac{4!}{1!(4-1)!} = 6 + 4 = 10 = \binom{5}{2}$$

Substituting this identity into the combined sum gives:

$$(z_1 + z_2)^{k+1} = \sum_{i=0}^{k+1} \binom{k+1}{i} z_1^{k+1-i} z_2^i$$

---

Visual Understanding

To visualize the process, think of the binomial coefficients as forming Pascal’s triangle:

$$\begin{array}{cccccc} & & & 1 & & \\ & & 1 & & 1 & \\ & 1 & & 2 & & 1 \\ 1 & & 3 & & 3 & & 1 \\ \end{array}$$

When you add two adjacent entries in row $k$, you get the entry directly below them in row $k+1$. For example:

• In row 3: $1 + 3 = 4$, $3 + 3 = 6$, $3 + 1 = 4$.
• This mirrors the identity $\binom{k+1}{i} = \binom{k}{i} + \binom{k}{i-1}$.

---

Additional Examples

Example 1: $k = 2$

Expand $(z_1 + z_2)^3$ using the formula:

$$(z_1 + z_2)^3 = \sum_{i=0}^3 \binom{3}{i} z_1^{3-i} z_2^i$$

From Pascal’s triangle:

$$\binom{3}{0} = 1, \ \binom{3}{1} = 3, \ \binom{3}{2} = 3, \ \binom{3}{3} = 1$$

Result:

$$(z_1 + z_2)^3 = z_1^3 + 3z_1^2z_2 + 3z_1z_2^2 + z_2^3$$

---

Final Remarks

Reindexing is a matter of carefully shifting the summation limits and adjusting the binomial coefficients or powers accordingly. The key to combining sums is ensuring both sums use the same index and limits. This process ties directly to the structure of Pascal's triangle, making the algebraic manipulation visually intuitive and mathematically rigorous.