Binomial Theorem

The Binomial Theorem

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

Expanded: $(x + y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \cdots + \binom{n}{n}y^n$

Common Expansions

$(x + y)^2$

$x^2 + 2xy + y^2$

$(x + y)^3$

$x^3 + 3x^2y + 3xy^2 + y^3$

$(x + y)^4$

$x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$

$(x - y)^n$

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

General Term

The $(k+1)$-th term in the expansion of $(x + y)^n$: $T_{k+1} = \binom{n}{k} x^{n-k} y^k$

Example: Find the 4th term of $(2x + 3)^7$:

• $k = 3$ (4th term) $T_4 = \binom{7}{3} (2x)^{7-3} (3)^3 = 35 \cdot 16x^4 \cdot 27 = 15120x^4$

Special Cases

Sum of Binomial Coefficients

Let $x = y = 1$: $(1 + 1)^n = \sum_{k=0}^{n} \binom{n}{k} = 2^n$

Alternating Sum

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

Sum of Even/Odd Coefficients

$\sum_{k \text{ even}} \binom{n}{k} = \sum_{k \text{ odd}} \binom{n}{k} = 2^{n-1}$

Binomial Identities

Pascal's Identity

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

Vandermonde's Identity

$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

Sum of Squares

$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$

Weighted Sum

$\sum_{k=0}^{n} k\binom{n}{k} = n \cdot 2^{n-1}$

$\sum_{k=0}^{n} k^2\binom{n}{k} = n(n+1) \cdot 2^{n-2}$

Multinomial Theorem

For $(x_1 + x_2 + \cdots + x_m)^n$: $(x_1 + x_2 + \cdots + x_m)^n = \sum \binom{n}{n_1, n_2, \ldots, n_m} x_1^{n_1} x_2^{n_2} \cdots x_m^{n_m}$

where the sum is over all non-negative integers $n_1, \ldots, n_m$ with $n_1 + n_2 + \cdots + n_m = n$.

Multinomial Coefficient

$\binom{n}{n_1, n_2, \ldots, n_m} = \frac{n!}{n_1! n_2! \cdots n_m!}$

Example: Expand $(x + y + z)^3$: $= x^3 + y^3 + z^3 + 3x^2y + 3x^2z + 3xy^2 + 3y^2z + 3xz^2 + 3yz^2 + 6xyz$

Applications

Counting Subsets

Coefficient of $x^k$ in $(1 + x)^n$ is $\binom{n}{k}$ = number of $k$-subsets.

Probability

In binomial distribution, $\binom{n}{k}p^k(1-p)^{n-k}$ is probability of $k$ successes in $n$ trials.

Combinatorial Proofs

Prove $\binom{n}{k} = \binom{n}{n-k}$:

Algebraic: $\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!k!} = \binom{n}{n-k}$

Combinatorial: Choosing $k$ elements to include is the same as choosing $n-k$ to exclude.

From Binomial Theorem: $(1+x)^n = (x+1)^n$

Coefficient of $x^k$ on left is $\binom{n}{k}$. Coefficient of $x^k$ on right (letting $x^k = x^{n-(n-k)}$) is $\binom{n}{n-k}$.

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)(\alpha-2)\cdots(\alpha-k+1)}{k!}$

Example: $(1+x)^{-1} = 1 - x + x^2 - x^3 + \cdots = \sum_{k=0}^{\infty} (-1)^k x^k$