Home >> Pre-Calculus >> 10. Sequences, Induction, and Probability

<< 10.4. Mathematical Induction

>> 10.6. Counting Principles: Permutations and Combinations

10.5. The Binomial Theorem

One of the most important theorems in mathematics is the * binomial theorem*. This theorem tells us how to expand an arbitrary power of a binomial, i.e. a mathematical expression consisting of the sum of two terms. Specifically, the binomial theorem is as follows:

**(10.5.1)**

Here, x and y are arbitary expressions, n is a fixed nonnegative integer, and the coefficients _{n}C_{k} (read as "n choose k") are positive integers known as * binomial coefficients*.

Before proving the binomial theorem, we need to define binomial coefficients. In the following section, we will interpret these coefficients in terms of counting combinations of objects, but for now, we just define them.

We begin with the binomial coefficient _{0}C_{0}, which we define to be equal to 1. Similarly, we define _{n}C_{0} and _{n}C_{n} to be equal to 1 for all nonnegative integers n. Now we need to define _{n}C_{k} for 0<k<n. We do so by defining _{n}C_{k} to be equal to the sum of _{n-1}C_{k-1} and _{n-1}C_{k}. In other words, the binomial coefficients satisfy the following two conditions:

**(10.5.2a)**_{n}C_{0}=_{n}C_{n}= 1 (n≥0)**(10.5.2b)**_{n}C_{k}=_{n-1}C_{k-1}+_{n-1}C_{k}(n≥1, 0<k<n)

From these two equations, we can construct all binomial coefficients, believe it or not! The way we do so is to construct a famous triangular array of numbers known as Pascal's Triangle, named after the 17th century French mathematician Blaise Pascal, who invented binomial coefficiets and probability theory. A diagram of the first 11 rows of Pascal's Triangle is shown below.

Figure 10.5.3: Pascal's Triangle

Note that the numbers along the left and right edges of Pascal's Triangle are all equal to 1. Also note that each number in the interior is equal to the sum of the two numbers next to it in the row above it. These are exactly the two defining properties (10.5.2a) and (10.5.2b) corresponding to binomial coefficients. Therefore, the numbers in Pascal's triangle are nothing but binomial coefficients. Specifically, the (k+1)st number in the (n+1)st row of Pascal's Triangle is equal to the binomial coefficient _{n}C_{k}.

**Example 1:** Use Pascal's Triangle to determine the following binomial coefficients:

- (a)
_{2}C_{1} - (b)
_{ 5}C_{3} - (c)
_{10}C_{7}

**Solution: **

- (a) The binomial coefficient
_{2}C_{1}is equal to the second number in the third row of Pascal's Triangle, which is 2. - (b) The binomial coefficient
_{5}C_{3}is equal to the fourth number in the sixth row of Pascal's Triangle, which is 10. - (c) The binomial coefficient
_{10}C_{7}is equal to the eighth number in the eleventh row of Pascal's Triangle, which is 120.

Note that for fixed n, the binomial coefficients _{n}C_{k} for k ranging from 0 to n are just the entries in the (n+1)st row of Pascal's Triangle. But these are precisely the coefficients appearing in Equation (10.5.1). Therefore, if we expand (x + y)^{n}, the coefficients in front of each monomial are just the entries in this row. Thus we have the following expansions:

(x + y)^{0} = 1x^{0}y^{0} = 1

(x + y)^{1} = 1x^{1}y^{0} + 1x^{0}y^{1} = x + y

(x + y)^{2} = 1x^{2}y^{0} + 2x^{1}y^{1} + 1x^{0}y^{2}= x^{2} + 2xy + y^{2}

(x + y)^{3} = 1x^{3}y^{0} + 3x^{2}y^{1} + 3x^{1}y^{2} + 1x^{0}y^{3} = x^{3} + 3x^{2}y + 3xy^{2}+ y^{3}

(x + y)^{4} = 1x^{4}y^{0} + 4x^{3}y^{1} + 6x^{2}y^{2} + 4x^{1}y^{3} + 1x^{0}y^{4}= x^{4} + 4x^{3}y + 6x^{2}y^{2}+ 4xy^{3} + y^{4}

etc.

So how do we prove the binomial theorem? We will prove it by mathematical induction. First we look at the base case, n = 0. It is clearly true that (x + y)^{0} = 1x^{0}y^{0} = 1, so this case checks out. Next we must follow the induction step, i.e. we must prove that Equation (10.5.1) holds for n+1, assuming that it holds for n. This amounts to the same thing as proving that it holds for n, assuming that it holds for n-1 (just replace n with n-1). Thus, we are assuming the following for some fixed n≥1:

Replacing k with k-1, i.e. by increasing the values of k by 1, we find that this equation also takes on the following form:

Next we compute (x + y)^{n} = (x + y)(x + y)^{n-1} = x(x + y)^{n-1} + y(x + y)^{n-1} by multiplying x by the first form of the binomial formula for (x + y)^{n-1}, multiplying y by the second form, and adding the results. Doing so, we find

Thus we see that assuming (10.5.1) holds for n-1 implies that it also holds for n. This completes the proof of the binomial theorem.

Home >> Pre-Calculus >> 10. Sequences, Induction, and Probability