Proofs of the Binomial Theorem

🔢 Proof 1: Combinatorial (Counting) Proof

The most intuitive proof uses the fundamental counting principle. Consider expanding (x + y)ⁿ as the product of n identical factors:

Key Insight

When multiplying this product, each term in the expansion is formed by choosing either x or y from each factor. To obtain a term of the form x^n−ky^k, we must:

1. Choose y from exactly k of the n factors
2. Choose x from the remaining n−k factors

Counting the Ways

The number of distinct ways to choose which k factors contribute y is given by the binomial coefficient:

Worked Example: Coefficient of x²y² in (x + y)⁴

🔄 Proof 2: Mathematical Induction

Proof by induction establishes the theorem for all nonnegative integers n using two key steps.

Step 1: Base Case (n = 0)

(x + y)⁰ = 1

Σ_k=0⁰ C(0,k) x⁰⁻ᵏ yᵏ = C(0,0) x⁰ y⁰ = 1

✅ Base case holds.

Step 2: Inductive Hypothesis

Assume for some n:

(x + y)ⁿ = Σ_k=0ⁿ C(n,k) xⁿ⁻ᵏ yᵏ

Step 3: Inductive Step

Prove for n + 1:

(x + y)ⁿ⁺¹ = (x + y)(x + y)ⁿ

= (x + y) × Σ_k=0ⁿ C(n,k) xⁿ⁻ᵏ yᵏ

= xΣ C(n,k)xⁿ⁻ᵏyᵏ + yΣ C(n,k)xⁿ⁻ᵏyᵏ

= Σ C(n,k)xⁿ⁻ᵏ⁺¹yᵏ + Σ C(n,k)xⁿ⁻ᵏyᵏ⁺¹

Step 4: Pascal's Identity

Using Pascal's Identity:

C(n,k) + C(n,k−1) = C(n+1,k)

We obtain:

(x + y)ⁿ⁺¹ = Σ_k=0ⁿ⁺¹ C(n+1,k) xⁿ⁺¹⁻ᵏ yᵏ

📐 Proof 3: Algebraic (Generating Functions)

This proof uses generating functions and formal power series.

The Generating Function Approach

(1 + x)ⁿ = (1 + x)(1 + x)⋯(1 + x)

When expanded, each term comes from choosing either 1 or x from each factor. The coefficient of xᵏ is exactly C(n,k).

Derivation

(1 + x)ⁿ = Σ_k=0ⁿ [n! / (k!(n−k)!)] × 1ⁿ⁻ᵏ × xᵏ

= Σ_k=0ⁿ C(n,k) xᵏ

Substituting x → y/x and multiplying by xⁿ:

(x + y)ⁿ = Σ_k=0ⁿ C(n,k) xⁿ⁻ᵏ yᵏ

Combinatorial Applications

• Subsets: C(n,k) = number of k-element subsets
• Lattice Paths: C(n,k) = paths from (0,0) to (k,n−k)
• Binary Strings: C(n,k) = strings of length n with k ones
• Polygon Diagonals: C(n,2) − n = diagonals in n-gon

🎲 Proof 4: Probability-Based Proof

Using expectation and linearity of expectation from probability theory.

Setup

n independent Bernoulli trials, success probability p. Let Xᵢ be indicator for success:

Xᵢ = 1 with prob p, 0 with prob (1−p)

Total successes: S = X₁ + X₂ + ⋯ + Xₙ

Computing E[(1 + t)ˢ]

E[(1 + t)ˢ] = ∏_i=1ⁿ E[(1 + t)ˣⁱ]

E[(1 + t)ˣⁱ] = (1−p) + p(1 + t) = 1 + pt

E[(1 + t)ˢ] = (1 + pt)ⁿ

Expanding the PMF

P(S = k) = C(n,k) pᵏ (1−p)ⁿ⁻ᵏ

E[(1 + t)ˢ] = Σ P(S=k)(1+t)ᵏ = Σ C(n,k)[p(1+t)]ᵏ(1−p)ⁿ⁻ᵏ

= (1−p + p + pt)ⁿ = (1 + pt)ⁿ

📊 Vandermonde's Identity

A powerful generalization of the binomial theorem:

Combinatorial Proof

Problem: Count ways to choose r items from m + n items.

Solution 1: Direct: C(m + n, r)

Solution 2: Choose k from first m and r−k from last n:

Σ_k=0^r C(m,k) × C(n,r−k)

Algebraic Proof

From (1 + x)ᵐ × (1 + x)ⁿ = (1 + x)ᵐ⁺ⁿ, the coefficient of xʳ is:

Σ_k=0^r C(m,k) × C(n,r−k) = C(m + n, r)

Special Cases

• Σ C(r,k)² = C(2r, r) when m = n = r
• Σ C(n,k)² = C(2n, n) when r = m = n

📜 History of the Proofs

🔗 Related Topics