Binomial Theorem

The binomial theorem (or binomial expansion) is a result of expanding the powers of binomials or sums of two terms. The coefficients of the terms in the expansion are the binomial coefficients $\binom{n}{k}$. The theorem and its generalizations can be used to prove results and solve problems in combinatorics, algebra, calculus, and many other areas of mathematics.

The binomial theorem generalizes special cases which are common and familiar to students of basic algebra:

$$\begin{aligned} (x+y)^1 &= x+y \\ (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 \\ &\vdots \\ \end{aligned}$$

The binomial theorem also helps explore probability in an organized way:

A friend says that she will flip a coin 5 times. Each time the coin comes up heads, she will give you $10, but each time the coin comes up tails, she gives nothing. What is the probability that you will win $30 playing this game?

---

The binomial theorem inspires something called the binomial distribution, by which we can quickly calculate how likely we are to win $30 (or equivalently, the likelihood the coin comes up heads 3 times). The binomial theorem tells us that ${5 \choose 3} = 10$ of the $2^5 = 32$ possible outcomes of this game have us win $30. Therefore, the probability we seek is

$$\frac{5 \choose 3}{2^5} = \frac{10}{32} = 0.3125.\ _\square$$

Let $n$ be a positive integer, and $x$ and $y$ real numbers (or complex numbers, or polynomials). The coefficient of $x^k y^{n-k}$, in the $k^\text{th}$ term in the expansion of $(x+y)^n$, is equal to $\binom{n}{k}$, where

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

So

$$(x+y)^n = \sum_{r=0}^n {n \choose r} x^{n-r} y^r = \sum_{r=0}^n {n \choose r} x^r y^{n-r}.\ _\square$$

The above expansion is known as binomial expansion.

OR

The binomial theorem states that for any positive integer $n$, we have

$$\begin{aligned} (x+y)^n &= \binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+ \cdots +\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n \\ \\ &= \sum\limits_{k=0}^{n}\binom{n}{k}x^{n-k}y^k. \end{aligned}$$

We can prove it by combinatorics:

One can establish a bijection between the products of a binomial raised to $n$ and the combinations of $n$ objects. Each product which results in $a^{n-k}b^k$ corresponds to a combination of $k$ objects out of $n$ objects. Thus, each $a^{n-k}b^k$ term in the polynomial expansion is derived from the sum of $\binom{n}{k}$ products. $_\square$

Or we can also prove it by induction:

The base case $n = 1$ is immediate. Now suppose the theorem is true for $(x+y)^{n-1}$. Then

$$\begin{aligned} (x+y)^n &= (x+y)(x+y)^{n-1} \\ &= (x+y)\bigg(\binom{n-1}{0} x^{n-1} + \binom{n-1}{1} x^{n-2}y + \cdots + \binom{n-1}{n-1}y^{n-1}\bigg) \\ &= x^n + \left( \binom{n-1}{0} + \binom{n-1}{1} \right) x^{n-1}y + \left( \binom{n-1}{1} + \binom{n-1}{2} \right) x^{n-2}y^2 \phantom{=} + \cdots + \left(\binom{n-1}{n-2} + \binom{n-1}{n-1} \right) xy^{n-1} + y^n \\ \end{aligned}$$

and now Pascal's identity applies:

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

So the right side simplifies to

$$x^n + \binom{n}{1} x^{n-1}y + \binom{n}{2} x^{n-2}y^2 + \cdots + \binom{n}{n-1}xy^{n-1} + y^n$$

as desired. $_\square$

Find the coefficient of $x^4$ in the expansion of $(x+1)^9$.

---

The coefficient of the $4^\text{th}$ term is equal to $\binom{9}{4}=\frac{9!}{(9-4)!4!}=126$. Therefore, the $4^\text{th}$ term of the expansion is $126\cdot x^4\cdot 1 = 126x^4$, where the coefficient is $126$. $_\square$

Show that $$2^n = \sum_{k=0}^n {n\choose k}.$$

---

Proof:
Set $x=y=1$ in the binomial series to get

$$(1+1)^n = \sum_{k=0}^n {n\choose k} (1)^{n-k}(1)^k \Rightarrow 2^n = \sum_{k=0}^n {n\choose k}.\ _\square$$

The following problem has a similar solution. Hint: try $x=1$ and $y = i$.

Now try the following problem:

Although the formula above is only applicable for binomials raised to an integer power, a similar strategy can be applied to find the coefficients of any linear polynomial raised to an integer power.

The power rule in differential calculus can be proved using the limit definition of the derivative and the binomial theorem. $\big($To find the derivative of $x^n$, expand the expression

$$\frac{(x+h)^n-x^n}{h} = \binom{n}{1}x^{n-1} + \binom{n}{2} x^{n-2}h + \cdots + \binom{n}{n} h^{n-1}$$

and take the limit as $h \to 0$. All the terms except the first term vanish, so the answer is $n x^{n-1}.\big)$

The general proof of the principle of inclusion and exclusion involves the binomial theorem. Recall that the principle states that for finite sets $A_i \ (i = 1,\ldots,n)$,

$$\begin{aligned} \left| \bigcup_{i=1}^n A_i \right| &= \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| \phantom{=} - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n|, \end{aligned}$$

where the sums on the right side are taken over all possible intersections of distinct sets.

Suppose an element in the union appears in $d$ of the $A_i$. Then it contributes $d$ to the first sum, $-\binom{d}{2}$ to the second sum, and so on, so the total contribution is

$$\sum_{i=1}^d (-1)^{i-1} \binom{d}{i} = 1 - \sum_{i=0}^d (-1)^i \binom{d}{i},$$

but the last sum is equal to $(1-1)^d = 0$ by the binomial theorem. So each element in the union is counted exactly once.

The fact that the Möbius function $\mu$ is the Dirichlet inverse of the constant function $\mathbf{1}(n) = 1$ is a consequence of the binomial theorem; see here for a proof.

If $p$ is a prime number, then $p$ divides all the binomial coefficients $\binom{p}{k}$, $1 \le k \le p-1$. (There is a $p$ in the numerator but none in the denominator.) So

$$(x+y)^p \equiv x^p + y^p \pmod p.$$

This fact is quite useful and has some rather fruitful generalizations to the theory of finite fields, where the function $x \mapsto x^p$ is called the Frobenius map. This fact (and its converse, that the above equation is always true if and only if $p$ is prime) is the fundamental underpinning of the celebrated polynomial-time AKS primality test.

The theorem as stated uses a positive integer exponent $n$. It turns out that there are natural generalizations of the binomial theorem in calculus, using infinite series, for any real exponent $\alpha$. That is,

$$(1+x)^\alpha = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k$$

for $|x|<1$, where

$$\binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}.$$

Some special cases of this result are examined in greater detail in the Negative Binomial Theorem and Fractional Binomial Theorem wikis.

These are the expansions of $(x+y)^n$ for small values of $n$:

$$\begin{aligned} (x+y)^0 &=& 1 \\ (x+y)^1 &=& x+y \\ (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 \\ &\vdots \end{aligned}$$

When we look at the coefficients in the expressions above, we will find the following pattern:

$$1\\ 1\quad 1\\ 1\quad 2 \quad 1\\ 1\quad 3 \quad 3 \quad 1\\ 1\quad 4 \quad 6 \quad 4 \quad 1\\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1\\ \vdots$$

This is called the Pascal's triangle.

The theorem identifies the coefficients of the general expansion of $(x+y)^n$ as the entries of Pascal's triangle.

Although the formula above is only applicable for binomials raised to an integer power, a similar strategy can be applied to find the coefficients of any linear polynomial raised to an integer power.

• Pascal's Triangle