Page 437 - Discrete Mathematics and Its Applications

416 6 / Counting

3

from each of the other two sums). This can be done in ways. Finally, the only way to obtain
1
3
a y term is to choose the y for each of the three sums in the product, and this can be done in
exactly one way. Consequently, it follows that
3
(x + y) = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y)
= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy
3
2
3
2
= x + 3x y + 3xy + y . ▲
We now state the binomial theorem.

THEOREM 1 THE BINOMIALTHEOREM Let x and y be variables, and let n be a nonnegative integer.
Then
n
n n n−j j n n n n−1 n n−1 n n
(x + y) = x y = x + x y + ··· + xy + y .
j 0 1 n − 1 n
j=0

Proof: We use a combinatorial proof. The terms in the product when it is expanded are of
y ,
y for j = 0, 1, 2,...,n. To count the number of terms of the form x
the form x n−j j n−j j
note that to obtain such a term it is necessary to choose n − j xs from the n sums (so that the
y is
other j terms in the product are ys). Therefore, the coefficient of x n−j j n , which is
n−j
n

equal to . This proves the theorem.
j
Some computational uses of the binomial theorem are illustrated in Examples 2–4.
4
EXAMPLE 2 What is the expansion of (x + y) ?
Solution: From the binomial theorem it follows that
4
4
4 4−j j
(x + y) = x y
j
j = 0
4 4 4 4 4

3
3
2 2
4
= x + x y + x y + xy + y 4
0 1 2 3 4
4
3
2 2
4
3
= x + 4x y + 6x y + 4xy + y . ▲
25
12 13
EXAMPLE 3 What is the coefficient of x y in the expansion of (x + y) ?
Solution: From the binomial theorem it follows that this coefficient is

25 25!
= = 5,200,300.
13 13! 12! ▲
25
12 13
EXAMPLE 4 What is the coefficient of x y in the expansion of (2x − 3y) ?
25
Solution: First, note that this expression equals (2x + (−3y)) . By the binomial theorem, we
have
25 25
j

(2x + (−3y)) 25 = (2x) 25−j (−3y) .
j
j = 0