Verifying the Binomial Formula with Mathematical Induction

The binomial formula states:

(z1+z2)n=∑k=0n(nk)z1n−kz2k(z_1 + z_2)^n = \sum_{k=0}^n \binom{n}{k} z_1^{n-k} z_2^k

where (nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!} and n=1,2,…n = 1, 2, \ldots. This is a powerful formula in algebra, expressing the expansion of (z1+z2)n(z_1 + z_2)^n as a sum of terms involving powers of z1z_1 and z2z_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 nn. The process involves two steps:

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

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

For n=1n = 1, the formula becomes:

(z1+z2)1=∑k=01(1k)z11−kz2k(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:
(z1+z2)1=z1+z2(z_1 + z_2)^1 = z_1 + z_2
  • Right-hand side:
∑k=01(1k)z11−kz2k=(10)z11z20+(11)z10z21\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, (10)=1\binom{1}{0} = 1 and (11)=1\binom{1}{1} = 1, so:

∑k=01(1k)z11−kz2k=1⋅z1+1⋅z2=z1+z2\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=kn = k, i.e.,

(z1+z2)k=∑j=0k(kj)z1k−jz2j(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+1n = k+1, i.e.,

(z1+z2)k+1=∑j=0k+1(k+1j)z1k+1−jz2j(z_1 + z_2)^{k+1} = \sum_{j=0}^{k+1} \binom{k+1}{j} z_1^{k+1-j} z_2^j

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

Using the distributive property of multiplication:

(z1+z2)k+1=(z1+z2)⋅(z1+z2)k(z_1 + z_2)^{k+1} = (z_1 + z_2) \cdot (z_1 + z_2)^k

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

(z1+z2)k+1=(z1+z2)⋅∑j=0k(kj)z1k−jz2j(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 z1+z2z_1 + z_2 across the summation:

(z1+z2)k+1=∑j=0k(kj)z1k−j+1z2j+∑j=0k(kj)z1k−jz2j+1(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+1i = j+1 (so j=i−1j = i-1):

∑j=0k(kj)z1k−jz2j+1=∑i=1k+1(ki−1)z1k+1−iz2i\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:

(z1+z2)k+1=∑j=0k(kj)z1k−j+1z2j+∑i=1k+1(ki−1)z1k+1−iz2i(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−1j = i-1:

(z1+z2)k+1=∑i=0k+1[(ki)+(ki−1)]z1k+1−iz2i(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 (k+1i)=(ki)+(ki−1)\binom{k+1}{i} = \binom{k}{i} + \binom{k}{i-1} allows us to simplify:

(z1+z2)k+1=∑i=0k+1(k+1i)z1k+1−iz2i(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+1n = 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:

(z1+z2)n=∑k=0n(nk)z1n−kz2k(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 nn. 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:

(z1+z2)k+1=∑j=0k(kj)z1k−j+1z2j+∑j=0k(kj)z1k−jz2j+1(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:

∑j=0k(kj)z1k−jz2j+1\sum_{j=0}^k \binom{k}{j} z_1^{k-j} z_2^{j+1}

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

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

Thus, the summation becomes:

∑j=0k(kj)z1k−jz2j+1=∑i=1k+1(ki−1)z1k+1−iz2i\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=0j = 0 to i=1i = 1.
  2. The upper limit changes from j=kj = k to i=k+1i = k+1.
  3. The binomial coefficient (kj)\binom{k}{j} is replaced with (ki−1)\binom{k}{i-1}, since j=i−1j = i-1.
  4. The powers of z1z_1 and z2z_2 are updated accordingly: z1k−jz_1^{k-j} becomes z1k+1−iz_1^{k+1-i}, and z2j+1z_2^{j+1} becomes z2iz_2^i.

Combining the Two Sums

Now the two summations can be written as:

  1. ∑j=0k(kj)z1k−j+1z2j\sum_{j=0}^k \binom{k}{j} z_1^{k-j+1} z_2^j,
  2. ∑i=1k+1(ki−1)z1k+1−iz2i\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 ii):

  • The first sum has j=ij = i, so it remains: ∑i=0k(ki)z1k+1−iz2i\sum_{i=0}^k \binom{k}{i} z_1^{k+1-i} z_2^i
  • The second sum starts at i=1i = 1 and ends at i=k+1i = k+1: ∑i=1k+1(ki−1)z1k+1−iz2i\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 ii. Thus, they can be combined into a single summation:

(z1+z2)k+1=∑i=0k+1[(ki)+(ki−1)]z1k+1−iz2i(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 (ki)+(ki−1)\binom{k}{i} + \binom{k}{i-1} is a fundamental identity of binomial coefficients. It states:

(k+1i)=(ki)+(ki−1)\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=4k = 4 and i=2i = 2, (42)+(41)=4!2!(4−2)!+4!1!(4−1)!=6+4=10=(52)\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:

(z1+z2)k+1=∑i=0k+1(k+1i)z1k+1−iz2i(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:

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

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

  • In row 3: 1+3=41 + 3 = 4, 3+3=63 + 3 = 6, 3+1=43 + 1 = 4.
  • This mirrors the identity (k+1i)=(ki)+(ki−1)\binom{k+1}{i} = \binom{k}{i} + \binom{k}{i-1}.

Additional Examples

Example 1: k=2k = 2

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

(z1+z2)3=∑i=03(3i)z13−iz2i(z_1 + z_2)^3 = \sum_{i=0}^3 \binom{3}{i} z_1^{3-i} z_2^i

From Pascal’s triangle:

(30)=1, (31)=3, (32)=3, (33)=1\binom{3}{0} = 1, \ \binom{3}{1} = 3, \ \binom{3}{2} = 3, \ \binom{3}{3} = 1

Result:

(z1+z2)3=z13+3z12z2+3z1z22+z23(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.


Comments

Post a Comment

Popular posts from this blog

What is Mathematical Fluency?

What does it really mean for students to be mathematically fluent? If you’ve been in any math PD over the past few years, you’ve likely heard the phrase everywhere. We talk about fluency as something students should develop, strengthen, and demonstrate, but it can still feel abstract when we try to describe it in observable, classroom-ready terms. This post breaks down mathematical fluency into the two simplest frames we can use as teachers: what it looks like and what it sounds like . These descriptions can guide instruction, assessment, student goal-setting, and even walkthrough conversations with colleagues or administrators. What Mathematical Fluency Looks Like In a classroom where students are developing mathematical fluency, you see students making choices about strategies rather than following steps robotically. They use representations—number lines, diagrams, tables, graphs, manipulatives, symbolic expressions—and switch between them to make sense of a problem. They move ...
Read more

Unlocking the Group: Cosets, Cayley’s Theorem, and Lagrange’s Theorem

Mathematics is full of elegant ideas that take simple definitions and build deep, powerful structures. In group theory, three such concepts—cosets, Cayley's Theorem, and Lagrange’s Theorem—form a foundational trio that unveils the internal symmetry of algebraic systems. Let’s explore what they mean and why they matter. What’s a Coset, Really? Imagine you have a group and a smaller subgroup inside it. Now, pick any element from the big group and use it to shift every element in the subgroup by multiplying on the left. The resulting set is called a left coset . You can also do this multiplication on the right, forming a right coset . These cosets aren’t usually groups themselves—but they do break the original group into equal-sized, non-overlapping pieces. Intuitively , cosets act like “shifts” of the subgroup across the whole group. Think of tiling a floor: each tile is a copy of the same shape (the subgroup) placed in different locations (cosets). Lagrange’s Theorem: Size Matt...
Read more