Combinatorial Probability - Key Proof

We present a complete proof of the binomial theorem using mathematical induction, one of the most important results connecting algebra and combinatorics.

Binomial Theorem

Theorem

For any real numbers $x, y$ and non-negative integer $n$ : $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$

Proof

We proceed by induction on $n$ .

Base Case ( $n = 0$ ): Both sides equal 1: $(x+y)^0 = 1 = \binom{0}{0} x^0 y^0$

Base Case ( $n = 1$ ): Both sides equal $x + y$ : $(x+y)^1 = x + y = \binom{1}{0} y + \binom{1}{1} x$

Inductive Step: Assume the formula holds for $n$ . We prove it for $n+1$ : $(x+y)^{n+1} = (x+y)(x+y)^n$

By the inductive hypothesis: $(x+y)^{n+1} = (x+y) \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$

Distribute $(x+y)$ : $= x \sum_{k=0}^n \binom{n}{k} x^k y^{n-k} + y \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$

$= \sum_{k=0}^n \binom{n}{k} x^{k+1} y^{n-k} + \sum_{k=0}^n \binom{n}{k} x^k y^{n-k+1}$

In the first sum, substitute $j = k+1$ (so $k = j-1$ ): $= \sum_{j=1}^{n+1} \binom{n}{j-1} x^j y^{n+1-j} + \sum_{k=0}^n \binom{n}{k} x^k y^{n+1-k}$

Combining sums (using $j$ as the index variable throughout): $= \binom{n}{n} x^{n+1} + \sum_{j=1}^n \left[\binom{n}{j-1} + \binom{n}{j}\right] x^j y^{n+1-j} + \binom{n}{0} y^{n+1}$

By Pascal's identity, $\binom{n}{j-1} + \binom{n}{j} = \binom{n+1}{j}$ , and using $\binom{n}{n} = \binom{n+1}{n+1} = 1$ and $\binom{n}{0} = \binom{n+1}{0} = 1$ :

$= \binom{n+1}{n+1} x^{n+1} + \sum_{j=1}^n \binom{n+1}{j} x^j y^{n+1-j} + \binom{n+1}{0} y^{n+1}$

$= \sum_{j=0}^{n+1} \binom{n+1}{j} x^j y^{n+1-j}$

This completes the induction. □

■

Combinatorial Interpretation

The binomial theorem also has a beautiful combinatorial proof. When expanding $(x+y)^n$ , we multiply $n$ factors of $(x+y)$ . Each term in the expansion comes from choosing either $x$ or $y$ from each factor.

To get a term $x^k y^{n-k}$ , we must choose $x$ from exactly $k$ of the $n$ factors. The number of ways to select which $k$ factors contribute $x$ is $\binom{n}{k}$ .

Example

Verify for $n = 3$ : $(x+y)^3 = (x+y)(x+y)(x+y)$

Expanding by choosing $x$ or $y$ from each factor:

Choose $x$ three times: $xxx = x^3$ (1 way: $\binom{3}{3} = 1$ )
Choose $x$ twice: $xxy, xyx, yxx = 3x^2y$ ( $\binom{3}{2} = 3$ ways)
Choose $x$ once: $xyy, yxy, yyx = 3xy^2$ ( $\binom{3}{1} = 3$ ways)
Choose $x$ zero times: $yyy = y^3$ (1 way: $\binom{3}{0} = 1$ )

Result: $(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$ ✓

Applications

Setting specific values in the binomial theorem yields useful identities:

$x = y = 1$ : $2^n = \sum_{k=0}^n \binom{n}{k}$ (Sum of binomial coefficients equals $2^n$ )

$x = 1, y = -1$ : $0 = \sum_{k=0}^n (-1)^k \binom{n}{k}$ (Alternating sum equals 0 for $n \geq 1$ )

$x = 1, y = 2$ : $3^n = \sum_{k=0}^n \binom{n}{k} 2^{n-k}$

Remark

The binomial theorem exemplifies the deep connection between algebra (polynomial expansion) and combinatorics (counting selections). This duality pervades discrete mathematics, where algebraic identities often have elegant combinatorial interpretations.