Page 561 - Discrete Mathematics and Its Applications

540 8 / Advanced Counting Techniques

Example 8 provides a useful formula for extended binomial coefficients when the top
parameter is a negative integer. It will be useful in our subsequent discussions.

EXAMPLE 8 When the top parameter is a negative integer, the extended binomial coefficient can be expressed
in terms of an ordinary binomial coefficient. To see that this is the case, note that

−n (−n)(−n − 1) ··· (−n − r + 1)
= by definition of extended binomial coefficient
r r!
r
(−1) n(n + 1) ··· (n + r − 1)
= factoring out –1 from each term in the numerator
r!
r
(−1) (n + r − 1)(n + r − 2) ··· n
= by the commutative law for multiplication
r!
r
(−1) (n + r − 1)!
= multiplying both the numerator and denominator
r!(n − 1)!
by (n − 1)!

n + r − 1
r
= (−1) by the definition of binomial coefficients
r
r
= (−1) C(n + r − 1,r). using alternative notation for binomial
coefficients
▲
We now state the extended binomial theorem.

THEOREM 2 THE EXTENDED BINOMIAL THEOREM Let x be a real number with |x| < 1 and
let u be a real number. Then

∞
u u k
(1 + x) = x .
k
k = 0

Theorem 2 can be proved using the theory of Maclaurin series. We leave its proof to the reader
with a familiarity with this part of calculus.

Remark: When u is a positive integer, the extended binomial theorem reduces to the binomial
u

theorem presented in Section 6.4, because in that case = 0if k> u.
k
Example 9 illustrates the use of Theorem 2 when the exponent is a negative integer.

EXAMPLE 9 Find the generating functions for (1 + x) −n and (1 − x) −n , where n is a positive integer, using
the extended binomial theorem.

Solution: By the extended binomial theorem, it follows that

∞
−n
−n k
(1 + x) = x .
k
k = 0