HOME

David Terr
Ph.D. Math, UC Berkeley

 

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) binomial theorem

Here, x and y are arbitary expressions, n is a fixed nonnegative integer, and the coefficients nCk (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 0C0, which we define to be equal to 1. Similarly, we define nC0 and nCn to be equal to 1 for all nonnegative integers n. Now we need to define nCk for 0<k<n. We do so by defining nCk to be equal to the sum of n-1Ck-1 and n-1Ck. In other words, the binomial coefficients satisfy the following two conditions:

  • (10.5.2a) nC0 = nCn = 1 (n≥0)
  • (10.5.2b) nCk = n-1Ck-1 + n-1Ck (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.

pascal's triangle

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 nCk.

 

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

  • (a) 2C1
  • (b) 5C3
  • (c) 10C7

Solution:

  • (a) The binomial coefficient 2C1 is equal to the second number in the third row of Pascal's Triangle, which is 2.
  • (b) The binomial coefficient 5C3 is equal to the fourth number in the sixth row of Pascal's Triangle, which is 10.
  • (c) The binomial coefficient 10C7 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 nCk 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 = 1x0y0 = 1

(x + y)1 = 1x1y0 + 1x0y1 = x + y

(x + y)2 = 1x2y0 + 2x1y1 + 1x0y2= x2 + 2xy + y2

(x + y)3 = 1x3y0 + 3x2y1 + 3x1y2 + 1x0y3 = x3 + 3x2y + 3xy2+ y3

(x + y)4 = 1x4y0 + 4x3y1 + 6x2y2 + 4x1y3 + 1x0y4= x4 + 4x3y + 6x2y2+ 4xy3 + y4

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 = 1x0y0 = 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:

binomial theorem for 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:

binomial theorem with n-1, second 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

binomial theorem proof

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

<< 10.4. Mathematical Induction

>> 10.6. Counting Principles: Permutations and Combinations