# Introduction to Proofs: An Active Exploration of Mathematical Language

## Section6.1Binomial Theorem

The Binomial Theorem has applications in many areas of mathematics, from calculus, to number theory, to probability. In this section we look at the connection between Pascal's triangle and binomial coefficients. We ultimately prove the Binomial Theorem using induction.

### Definition6.1.1.

Let $$n, r$$ be nonnegative integers with $$r\leq n\text{.}$$ An $$r$$-combination of a set of $$n$$ elements is the number of subsets of size $$r$$ that can be chosen from a set of $$n$$ elements. We will use the notation $$\binom{n}{r}\text{.}$$
Other common notations are $$C(n, r)$$ or $$nCr\text{.}$$
For reasons we will see later in this section, $$\binom{n}{r}$$ are also called binomial coefficients.
We can calculate combinations or binomial coefficients using the formula
\begin{equation*} \binom{n}{r}=\frac{n!}{r!(n-r)!}\text{.} \end{equation*}
Using the definition that $$0!=1\text{,}$$ we can see that $$\binom{n}{0}=1$$ and $$\binom{0}{0}=1\text{.}$$
Calculate $$\binom{5}{4}\text{,}$$ the number of subsets of size 4 chosen from a set of 5 elements.
Using the formula,
\begin{equation*} \binom{5}{4}=\frac{5!}{4!(5-4)!}=\frac{5!}{4!1!} \end{equation*}
\begin{equation*} =\frac{(5)(4)(3)(2)(1)}{(4)(3)(2)(1)(1)}=5 \end{equation*}
This means there are 5 different subsets with 4 elements of any set with 5 elements.

### Activity6.1.1.Calculating Binomial Coefficients.

Calculate the following binomial coefficients.

#### (a)

Calculate $${6 \choose 2}\text{.}$$

#### (b)

Calculate $${6 \choose 4}\text{.}$$

#### (c)

Calculate $${4 \choose 0}\text{.}$$

#### (d)

Calculate $${4 \choose 4}\text{.}$$
The proof of Theorem 6.1.3 is left as an exercise.

### Activity6.1.2.Proof of Pascal's Formula.

Give an algebraic proof for Pascal's Formula:
\begin{equation*} {{n+1}\choose {r}}={n\choose {r-1}}+{n \choose r}. \end{equation*}
Hint.
Start with the right-hand side. Use the definition of “choose,” then find a common denominator. Note, you will save yourself a lot of work if you find the least common denominator.
There is a connection between binomial coefficients and Pascal's triangle.
You may have seen Pascal's triangle before, the start of which is
 1 1 1 1 2 1 1 3 3 1
We get the numbers in each row by adding the two numbers above. If there is only one number, you just get 1. For example, the fourth row is 1, 3, 3, 1, since $$1+2=3\text{.}$$ The next row would be 1, 4, 6, 4, 1.
If we think about the first row as actually being the 0th row, we can make a triangle with the binomial coefficients:
 $$\binom{0}{0}$$ $$\binom{1}{0}$$ $$\binom{1}{1}$$ $$\binom{2}{0}$$ $$\binom{2}{1}$$ $$\binom{2}{2}$$ $$\binom{3}{0}$$ $$\binom{3}{1}$$ $$\binom{3}{2}$$ $$\binom{3}{3}$$
If you calculate the binomial coefficients, you will see that you get the same values as Pascal's triangle. Furthermore, Pascal's formula, Theorem 6.1.4, is just the rule we use to get the triangle: add the $$r-1$$ and $$r$$ terms from the $$n^{th}$$ row to get the $$r$$ term in the $$n+1$$ row.
Why do we call $$\binom{n}{r}$$ a binomial coefficient? First, a binomial is an expression of the form $$a+b\text{.}$$ We will see that the Binomial Theorem gives a formula for calculating $$(a+b)^n\text{.}$$ The coefficients in this formula are the binomial coefficients.
Suppose we want to expand (or multiply) $$(a+b)^3=(a+b)(a+b)(a+b)\text{.}$$ We can think of the multiplication in this way:
• there is 1 way to get $$a^3\text{:}$$ choose 0 $$b$$'s from the three factors.
• there are 3 ways to get $$a^2b\text{:}$$ choose 1 $$b$$ from the three factors.
• there are 3 ways to get $$ab^2\text{:}$$ choose 2 $$b$$'s' from the three factors.
• there is 1 way to get $$b^3\text{:}$$ choose 3 $$b$$'s from the three factors.
This give us
\begin{equation*} (a+b)^3=\binom{3}{0}a^3+\binom{3}{1}a^2b+\binom{3}{2}ab^2+\binom{3}{3}b^3. \end{equation*}
Example 6.1.5 can be generalized to $$(a+b)^n$$ in the Binomial Theorem.
We can generalize the counting argument from Example 6.1.5 to prove the Binomial Theorem. This is the type of proof you would encounter in a course which emphasizes counting techniques. However, we can also prove the Binomial Theorem using induction, which is more appropriate for this course.
Prove
\begin{equation*} (a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^{n-i}b^i \end{equation*}
by induction on $$n\text{.}$$
Base step: Let $$n=0\text{.}$$ Then
\begin{equation*} (a+b)^0=1\text{.} \end{equation*}
Also,
\begin{equation*} \sum_{i=0}^{0}\binom{0}{i}a^{0-i}b^i=a^0b^0=1. \end{equation*}
Induction step: Assume $$(a+b)^k=\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\text{.}$$
Show $$(a+b)^{k+1}=\sum_{i=0}^{k+1}\binom{k+1}{i}a^{k+1-i}b^i$$
\begin{align*} (a+b)^{k+1}&=(a+b)^k(a+b)\\ &=\biggl(\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\biggr)(a+b)\\ &=a\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i+b\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\\ &=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^{i+1} \end{align*}
Now we want to change the index of the second sum. This is just a substitution of variable that allows us to shift how we index the terms. If we were to write out the sum, rather than have it in summation notation, we would not need this step. But it allows us to easily combine like terms in the two summations. So, in the second sum, let $$j=i+1\text{,}$$ so when $$i=0, j=1\text{;}$$ when $$i=k, j=k+1\text{,}$$ and $$i=j-1\text{.}$$ We get
\begin{align*} (a+b)^{k+1}&=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^{i+1}\\ &=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{j=1}^{k+1}\binom{k}{j-1}a^{k+1-j}b^j\\ &=a^{k+1}+\sum_{i=1}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{j=1}^{k}\binom{k}{j-1}a^{k+1-j}b^j+b^{k+1}\\ &\text{where we pulled out the first term of the first sum}\\ &\text{and the last term of the second sum}\\ &=a^{k+1}+\sum_{i=1}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=1}^{k}\binom{k}{i-1}a^{k+1-i}b^i+b^{k+1}\\ &\text{where we just relabeled the index in the second sum}\\ &=a^{k+1}+\sum_{i=1}^{k}\biggl[\binom{k}{i}+\binom{k}{i-1}\biggr]a^{k+1-i}b^i+b^{k+1}\\ &\text{where we combined like terms in the two sums}\\ &=a^{k+1}+\sum_{i=1}^{k}\binom{k+1}{i}a^{k+1-i}b^i+b^{k+1}\\ &\text{by Pascal's Formula}\\ &=\sum_{i=0}^{k+1}\binom{k+1}{i}a^{k+1-i}b^i \end{align*}

### Activity6.1.3.Understanding the Binomial Theorem.

Show the Binomial Theorem holds for $$n=2$$ and $$n=3\text{.}$$
Express the sum, $$\sum_{i=0}^{n}\binom{n}{i}x^i\text{,}$$ in closed form.
We think of writing out the sum as expanding, so the closed form means the power of a binomial.
For problems such as this, we need to identify $$a$$ and $$b$$ as in the Binomial Theorem.
We can see that $$x=b\text{.}$$ Since there does not appear to be any term for $$a\text{,}$$ we can let $$a=1\text{.}$$ Thus, the closed form is $$(1+x)^n\text{.}$$

### Activity6.1.4.An Expanded Form.

Use the Binomial Theorem to find $$(3-2x)^3\text{.}$$
Hint.
In this expression, what are $$a, b, n\text{?}$$

### Activity6.1.5.Powers of 2.

Prove $$2^n=\sum_{k=0}^n{n \choose k}\text{.}$$
Hint.
Use that $$2=(1+1)\text{.}$$

### ExercisesExercises

#### 1.

Give an algebraic proof for the formula:
\begin{equation*} {{n}\choose {r}}={n\choose {n-r}} \end{equation*}
for integers $$n$$ and $$r$$ with $$0\leq r\leq n\text{.}$$

#### 2.

1. Use Pascal’s triangle to compute the values of $${6\choose 2}, {6\choose 3}, {6\choose 4}$$ and $${6\choose 5}$$
2. Use the result of part (a) and Pascal’s Formula to compute $${7\choose 3}\text{,}$$ $${7\choose 4}\text{,}$$ and $${7\choose 5}\text{.}$$
3. Complete the row of Pascal’s triangle that corresponds to $$n=7\text{.}$$

#### 3.

The row of Pascal’s triangle that corresponds to $$n=8$$ is
\begin{equation*} 1\ \ \ 8\ \ \ 28\ \ \ 56\ \ \ 70\ \ \ 56\ \ \ 28\ \ \ 8\ \ \ 1. \end{equation*}
What is the row that corresponds to $$n=9\text{?}$$

#### 4.

Use the Binomial Theorem to expand $$(u-v)^5\text{.}$$

#### 5.

Use the Binomial Theorem to expand $$(p-2q)^4\text{.}$$

#### 6.

Find the coefficient of $$x^6y^3$$ in $$(x+y)^9\text{.}$$

#### 7.

Find the coefficient of $$x^7$$ in $$(2x+3)^{10}\text{.}$$

#### 8.

Express $$\sum_{k=0}^n{n\choose k}5^k$$ in closed form (without the summation symbol and without ellipses,…).

#### 9.

Express $$\sum_{k=0}^m{m\choose k}2^{m-k}x^k$$ in closed form (without the summation symbol and without ellipses,…).

#### 10.

Use Pascal’s Formula to prove by mathematical induction that if $$n$$ is an integer and $$n\geq 1\text{,}$$ then
\begin{equation*} \sum_{i=2}^{n+1}{i\choose 2}={2\choose 2}+{3\choose 2}+\ldots +{{n+1}\choose 2}={{n+2}\choose 3}. \end{equation*}

#### 11.

Use the Binomial Theorem to prove for all integers $$n\geq 1\text{,}$$
\begin{equation*} {n\choose 0}-{n\choose 1}+{n\choose 2}-\ldots +(-1)^n{n\choose n}=0. \end{equation*}
Hint.
Use the fact that $$1+(-1)=0\text{.}$$

#### 12.

Use the Binomial Theorem to prove for all integers $$n\geq 0\text{,}$$
\begin{equation*} 3^n={n\choose 0}+2{n\choose 1}+2^2{n\choose 2}+\ldots +2^n{n\choose n}. \end{equation*}