Binomial Theorem

The binomial theorem is one of the most fundamental results in combinatorics, providing an explicit expansion of powers of binomials in terms of binomial coefficients. This theorem has profound connections to algebra, analysis, and probability theory.

TheoremBinomial Theorem

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

where $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ is the binomial coefficient.

Proof

We prove this by induction on $n$ .

Base case: For $n = 0$ , we have $(x+y)^0 = 1 = \binom{0}{0}x^0y^0$ , which is true.

Inductive step: Assume the theorem holds for some $n \geq 0$ . We must show it holds for $n+1$ : $(x+y)^{n+1} = (x+y)(x+y)^n = (x+y)\sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$

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

Reindexing the second sum by setting $j = k+1$ : $= \sum_{k=0}^n \binom{n}{k} x^{n-k+1} y^k + \sum_{j=1}^{n+1} \binom{n}{j-1} x^{n-j+1} y^j$

Separating the first and last terms: $= \binom{n}{0}x^{n+1} + \sum_{k=1}^n \left[\binom{n}{k} + \binom{n}{k-1}\right] x^{n-k+1} y^k + \binom{n}{n}y^{n+1}$

Using Pascal's identity $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ and noting $\binom{n}{0} = \binom{n+1}{0} = 1$ and $\binom{n}{n} = \binom{n+1}{n+1} = 1$ : $= \sum_{k=0}^{n+1} \binom{n+1}{k} x^{n+1-k} y^k$

This completes the induction.

■

ExampleSpecial Cases and Applications

Setting specific values for $x$ and $y$ yields important identities:

Sum of binomial coefficients: Set $x = y = 1$ : $2^n = \sum_{k=0}^n \binom{n}{k}$
Alternating sum: Set $x = 1, y = -1$ : $0 = \sum_{k=0}^n (-1)^k \binom{n}{k}$ for $n \geq 1$
Powers of sums: For integers, $(x+y)^n$ gives the expansion directly. $(1+x)^3 = 1 + 3x + 3x^2 + x^3$
Vandermonde's identity: Comparing coefficients in $(1+x)^{m+n} = (1+x)^m(1+x)^n$ : $\binom{m+n}{k} = \sum_{j=0}^k \binom{m}{j}\binom{n}{k-j}$

Remark

The binomial theorem generalizes to non-integer exponents through Newton's generalized binomial theorem. For any real $\alpha$ and $|x| < 1$ : $(1+x)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k} x^k$ where $\binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}$ is the generalized binomial coefficient.

This leads to important series expansions, such as: $(1+x)^{-1} = \sum_{k=0}^\infty (-1)^k x^k = 1 - x + x^2 - x^3 + \cdots$

TheoremMultinomial Theorem

The binomial theorem extends to sums of more than two terms. For non-negative integers $n$ and any $m$ terms: $(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} \binom{n}{k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$

where $\binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$ is the multinomial coefficient, counting ways to partition $n$ objects into $m$ labeled groups of sizes $k_1, \ldots, k_m$ .

The binomial theorem provides a bridge between algebra and combinatorics: the algebraic expansion $(x+y)^n$ corresponds to choosing $k$ factors to contribute $y$ from $n$ total factors, which is precisely $\binom{n}{k}$ .