# 6 Binomial Theorem

The Binomial Theorem is useful in developing theory around the Binomial and Hypergeometric Distributions. Two proofs of the Theorem are provided here; one using the traditional approach, and one using a more general approach. Other useful theorems are provided at the end of this chapter.

### 6.1.1 Lemma: Pascal’s rule

Let $$n$$ and $$x$$ be non-negative integers such that $$x\leq n$$.

Then $${n-1\choose x} + {n-1\choose x-1} = {n\choose x}$$.

Proof:

\begin{aligned} {n-1\choose x} + {n-1\choose x-1} &= \frac{(n-1)!}{x!(n-1-x)!} + \frac{(n-1)!}{(x-1)!((n-1)-(x-1))!}\\ &= \frac{(n-1)!}{x!(n-x-1)!} + \frac{(n-1)!}{(x-1)!(n-1-x+1)!}\\ &= \frac{(n-1)!}{x!(n-x-1)!} + \frac{(n-1)!}{(x-1)!(n-x)!}\\ &= \frac{(n-1)!}{x(x-1)!(n-x-1)!} + \frac{(n-1)!}{(x-1)!(n-x)(n-x-1)!}\\ &= \frac{x(n-1)!}{x(x-1)!(n-x)(n-x-1)!} +\frac{(n-x)(n-1)!}{x(x-1)!(n-x)(n-x-1)!}\\ &= \frac{x(n-1)!+(n-x)(n-1)!}{x(x-1)!(n-x)(n-x-1)!} \\ &= \frac{(x+n-x)(x-1)!}{x(x-1)!(n-x)(n-x-1)!}\\ &= \frac{n(n-1)!}{x(x-1)!(n-x)(n-x-1)!} \\ &= \frac{n!}{x!(n-x)!} \\ &= {n\choose x} \end{aligned}

### 6.1.2 The Binomial Theorem

Let $$a$$ and $$b$$ be constants and let $$n$$ be any positive integer. Then

$(a+b)^n = \sum\limits_{x=0}^{n} {n\choose x} a^{n-x} b^x$

Proof:

This proof is completed by mathematical induction.

Base Step: $$n=1$$

\begin{aligned} (a+b)^1 &= \sum\limits_{x=0}^{1} {1\choose x} a^{1-x} b^x \\ &= {1\choose 0} a^{1-0} b^0 + {1\choose 1} a^{1-1} b^1 \\ &= 1\cdot a\cdot 1 + 1\cdot 1\cdot b \\ &= a+b \end{aligned}

Inductive Step: Assume that the Theorem holds for $$n$$, and show it is true for $$n+1$$.

\begin{aligned} (a+b)^{n+1} &= (a+b)(a+b)^n \\ &= a(a+b)^n + b(a+b)^n \\ &= a(a^n + \sum\limits_{x=1}^{n-1}{n\choose x}a^{n-x}b^x + b^n) + b(a^n + \sum\limits_{x=1}^{n-1}{n\choose x}a^{n-x}b^x+b^n) \\ &= (a^{n+1}+a\sum\limits_{x=1}^{n-1}{n\choose x}a^{n-x}ab^x) + (a^nb+\sum\limits_{x=1}^{n-1}{n\choose x}a^{n-x}b^x+b^{n+1}) \\ &= (a^{n+1}+\sum\limits_{x=1}^{n-1}{n\choose x}a^{n-x+1}ab^x) + (a^nb+\sum\limits_{x=1}^{n-1}{n\choose x}a^{n-x}b^{x+1}+b^{n+1}) \\ ^{[1]} &= (a^{n+1}+\sum\limits_{x=1}^{n}a^{n-x+1}b^x) + (\sum\limits_{x=0}^{n-1}{n\choose x}a^{n-x}b^{x+1}+b^{n+1}) \\ ^{[2]} &= (a^{n+1}+\sum\limits_{x=1}^{n}{n\choose x}a^{n-x+1}b^x) + \sum\limits_{x-1}^{n-1}{n\choose x-1}a^{n-x+1}b^{x+1-1}+b^{n+1}) \\ ^{[3]} &= a^{n+1} + \sum\limits_{x+1}^{n}{n+1\choose x}a^{n-x+1}b^x + b^{n+1} \\ &=a^{n+1}+\sum\limits_{x=1}^{n}{n+1\choose x}a^{(n+1)-x}b^x+b^{n+1} \\ ^{[4]} &= \sum\limits_{x=0}^{n+1}{n+1\choose x}a^{(n+1)-x}b^x \end{aligned}

This completes both the inductive step and the proof.

1. $$ab^n={n\choose n}a^{n-n+1}b^n$$ which is the term for $$x=n$$ in the first summation.
$$a^nb={n\choose 0}a^{n-0}b^1$$ which is the term for $$x=0$$ in the second summation.
2. $$\sum\limits_{x=0}^{n-1}{n\choose x}a^{n-x}b^{x+1} \\ \ \ \ \ = \sum\limits_{x=1}^{n}{n\choose x-1}a^{n-(x-1)}b^{(x-1)+1} \\ \ \ \ \ = \sum\limits_{x=1}^{n}{n\choose x-1}a^{n-x+1}b^x$$
3. This step is made using Pascal’s Rule with $$n=n-1$$.
4. $$a^{n+1}={n+1\choose 0}a^{(n+1)-0}b^0$$ which is the term for $$x=0$$ in the summation.
$$\ \ b^{n+1}={n+1\choose n+1}a^{(n+1)-(n+1)}b^{n+1}$$ which is the term for $$x=n+1$$ in the summation

## 6.2 General Approach

### 6.2.1 A Binomial Expansion Theorem

This theorem and its corrolary are provided by Brunette (Brunette 2003–2007a).

For any positive integer $$n$$, let $$B_n = (x_1+y_1) (x_2+y_2) \cdots (x_n+y_n)$$. In the expansion $$B_n$$, before combining possible like terms, the following are true:

1. There will be $$2^n$$ terms.
2. Each of these terms will be a product of $$n$$ factors.
3. In each such product there will be one factor from each binomial (in $$B_n$$).
4. Every such product of $$n$$ factors, one from each binomial, is represented in the expansion.

Proof:

Proof is done by induction.

For the case $$n=1$$, the result is clear.

Now assume that the theorem is true for a particular $$n$$ and consider $$B_{n+1}$$.

$B_{n+1} = B_n(x_{n+1} + y_{n+1}) = B_nx_{n+1} + B_ny_{n+1}$

By the inductive assumption, $$B_n = T_1 + T_2 + \cdots + T_{2^n}$$ where each $$T_i$$ is a product of $$n$$ factors, one factor from each binomial. It follows that every term in the expansion of $$B_n+1$$ is either of the type $$T_ix_{n+1}$$ or $$T_iy_{n+1}$$, for some $$1\leq i \leq 2^n$$. But each term of either of the above types is clearly a product of $$n+1$$ factors with one factor coming from each binomial. thus, if (ii) and (iii) are true for $$B_n$$, then they are true for $$B_n+1$$.

Next, by the inductive assumption, the expansion of $$B_n$$ is a sum of $$2^n+2^n$$ terms, i.e., $$2^{n+1}$$ terms. This completes the inductive step for (i).

Lastly, it remains for us to consider a product of the type $$p_1 p_2 \cdots p_n p_{n+1}$$ where, for each $$1\leq i\leq n+1$$, $$p_i = x_i$$ or $$p_i = y_i$$. By the inductive hypothesis, $$p_1 p_2 \cdots p_n$$ is a term in the expansion of $$B_n$$. If $$p_{n+1} = x_{n+1}$$, then $$p_1 p_2 \cdots p_n p_{n+1}$$ is a term in the expansion of $$B_nx_{n+1}$$, and so of $$B_{n+1}$$. Likewise, if $$p_{n+1}=y_{n+1}$$, then $$p_1 p_2 \cdots p_n p_{n+1}$$ is a term in the expansion of $$B_n y_{n+1}$$, and so of $$B_{n+1}$$. This completes the inductive step and the proof.

### 6.2.2 Corollary: Binomial Theorem

Let $$x$$ and $$y$$ be constants and let $$n$$ be any positive integer.

Then $$\displaystyle (x+y)^n = \sum\limits_{i=0}^{n} {n\choose i} x^{n-i} y^i\\$$

Proof:

Since each term in the expansion will have $$n$$ terms, each term must follow the form $$x^{n-i} y^i$$ for $$0 \leq i \leq n$$, and in all, there are $$2^n$$ such terms. For any given value of $$i$$, the number of terms of the form $$x^{n-i}y^i$$ is clearly the number of ways one can choose the $$i$$ factors of $$y$$ from the $$n$$ available binomials, i.e., $${n\choose i}$$, which gives

$(x+y)^n = \sum\limits_{i=0}^{n}{n\choose i} x^{n-i} y^i$

## 6.3 Other Theorems

### 6.3.1 Theorem

${N_1\choose 0}{N_2\choose n} + {N_1\choose 2}{N_2\choose n-1} + \cdots + {N_1\choose n-1}{N_2\choose 1} + {N_1\choose n}{N_2\choose 0} = {N_1+N_2\choose n}$

where $$0 \leq n \leq N_1 + N_2$$.

Proof:

Using the Binomial Theorem we establish

$(1+a)^{N-1} (1+a)^{N_2} = (1+a)^{N_1+N_2} \\ \Rightarrow [{N_1\choose 0}a^0+\cdots+{N_1\choose N_1}a^{N_1}]\cdot [{N_2\choose 0}a^0+\cdots+{N_2\choose N_2}a^{N_2}] \\ \ \ \ \ ={N_1+N_2\choose 0}+{N_1+N_2\choose 1}a+\cdots +{N_1+N_2\choose N_1+N_2}a^{N_1+N_2}$

Expanding the left side of the equation gives

${N_1\choose 0}{N_2\choose 0} + {N_1\choose 0}{N_2\choose 1}a + \cdots + {N_1\choose 0}{N_2\choose N_2}a^{N_2} + {N_1\choose 1}{N_2\choose 0}a \\ \ \ \ \ + \cdots + {N_1\choose 1}{N_2\choose N_2}a^{N_2+1} + \cdots + {N_1\choose N_1}{N_2\choose 0}a^{N_1} + {N_1\choose N_1}{N_2\choose 1}a^{N_1+1} \\ \ \ \ \ + \cdots + {N_1\choose N_1}{N_2\choose N_2}a^{N_1+N_2} \\ = {N_1\choose 0}{N_2\choose 0}+{N_1\choose 0}{N_2\choose 1}a + {N_1\choose 1}{N_2\choose 0}a \\ \ \ \ \ + {N_1\choose 0}{N_2\choose 2}a^2+{N_1\choose 1}{N_2\choose 1}a^2 + {N_1\choose 2}{N_2\choose 0}a^2 \\ \ \ \ \ + \cdots + {N_1\choose N_1}{N_2\choose N_2}a^{N_1+N_2}$

Notice that for any $$n$$ where $$0 \leq n \leq N_1 + N_2$$, the coefficient for $$a^n$$, found by combining like terms, is $${N_1\choose 0}{N_2\choose n} + {N_1\choose 1}{N_2\choose n-1} + \cdots+{N_1\choose n-1}{N_2\choose 1} + {N_1\choose 0}{N_2\choose n}$$ and, by the equivalence of the first equation in the proof, is equal to the coefficient $${N_1 + N_2\choose n}$$.

### 6.3.2 Theorem

$\frac{\sum\limits_{i=1}^{n}{N_1\choose i}{N_2\choose n-i}}{{N_1+N_2\choose n}} = 1$

for $$0 \leq n \leq N_1 + N_2$$.\

Proof:

Theorem 6.3.1 establishes the equality

${N_1\choose 0}{N_2\choose n}+{N_1\choose 2}{N_2\choose n-1} + \cdots + {N_1\choose n-1}{N_2\choose 1}+{N_1\choose n}{N_2\choose 0} = {N_1+N_2\choose n} \\ \Rightarrow\sum\limits_{i=1}^{n}{N_1\choose i}{N_2\choose n-i} = {N_1+N_2\choose n} \\ \Rightarrow\frac{\sum\limits_{i=1}^{n} {N_1\choose i}{N_2\choose n-i}} {{N_1+N_2\choose n}} = 1$

### References

Brunette, John. 2003–2007a. “A Binomial Expansion Theorem with the Binomial Theorem as a Corrolary.” Lecture Notes.