Page 572 - Discrete Mathematics and Its Applications

8.4 Generating Functions 551

35. Use generating functions to solve the recurrence rela- The exponential generating function for the sequence {a n }
tion a k = 5a k−1 − 6a k−2 with initial conditions a 0 = 6 is the series
and a 1 = 30. ∞

a n n
36. Use generating functions to solve the recurrence relation n! x .
k
a k = a k−1 + 2a k−2 + 2 with initial conditions a 0 = 4 n = 0
and a 1 = 12.
For example, the exponential generating function for the
37. Use generating functions to solve the recurrence relation sequence 1, 1, 1,... is the function ∞ x /n!= e .
n
x
n = 0
2
a k = 4a k−1 − 4a k−2 + k with initial conditions a 0 = 2 (You will find this particular series useful in these exercises.)
and a 1 = 5. x
Note that e is the (ordinary) generating function for the se-
38. Use generating functions to solve the recurrence re- quence 1, 1, 1/2!, 1/3!, 1/4!,....
k
lation a k = 2a k−1 + 3a k−2 + 4 + 6 with initial condi- 45. Find a closed form for the exponential generating func-
tions a 0 = 20, a 1 = 60. tion for the sequence {a n }, where
39. Use generating functions to find an explicit formula for a) a n = 2. b) a n = (−1) .
n
n
the Fibonacci numbers. c) a n = 3 . d) a n = n + 1.
∗ 40. a) Show that if n is a positive integer, then e) a n = 1/(n + 1).
46. Find a closed form for the exponential generating func-

2n
tion for the sequence {a n }, where
−1/2 n
= . n
n (−4) n a) a n = (−2) . b) a n =−1.
c) a n = n. d) a n = n(n − 1).
b) Use the extended binomial theorem and part (a) to e) a n = 1/((n + 1)(n + 2)).
n
show that the coefficient of x in the expansion of 47. Find the sequence with each of these functions as its ex-
2n
(1 − 4x) −1/2 is for all nonnegative integers n.
n ponential generating function.
∗ 41. (Calculus required) Let {C n } be the sequence of Catalan a) f(x) = e −x b) f(x) = 3x 2x
numbers, that is, the solution to the recurrence relation c) f(x) = e 3x − 3e 2x d) f(x) = (1 − x) + e −2x
n−1 −2x
C n = k = 0 C k C n−k−1 with C 0 = C 1 = 1 (see Exam- e) f(x) = e − (1/(1 − x))
ple 5 in Section 8.1). f) f(x) = e −3x − (1 + x) + (1/(1 − 2x))
2
a) Show that if G(x) is the generating function for the se- g) f(x) = e x
2
quence of Catalan numbers, then xG(x) − G(x) + 48. Find the sequence with each of these functions as its ex-
1 = 0. Conclude (using the initial conditions) that ponential generating function.
√
G(x) = (1 − 1 − 4x)/(2x). a) f(x) = e 3x b) f(x) = 2e −3x+1
b) Use Exercise 40 to conclude that c) f(x) = e 4x + e −4x d) f(x) = (1 + 2x) + e 3x
x
e) f(x) = e − (1/(1 + x))
∞
1 2n n x x 3
G(x) = x , f) f(x) = xe g) f(x) = e
n + 1 n
n = 0 49. A coding system encodes messages using strings of octal
(base 8) digits.A codeword is considered valid if and only
so that
if it contains an even number of 7s.
1 2n
C n = . a) Find a linear nonhomogeneous recurrence relation for
n + 1 n the number of valid codewords of length n. What are
c) Show that C n ≥ 2 n−1 for all positive integers n. the initial conditions?
b) Solve this recurrence relation usingTheorem 6 in Sec-
42. Use generating functions to prove Pascal’s identity:
tion 8.2.
C(n, r) = C(n − 1,r) + C(n − 1,r − 1) when n and r c) Solve this recurrence relation using generating func-
are positive integers with r< n.[Hint: Use the identity tions.
n
(1 + x) = (1 + x) n−1 + x(1 + x) n−1 .]
∗ 50. A coding system encodes messages using strings of
43. Use generating functions to prove Vandermonde’s iden-
r base 4 digits (that is, digits from the set {0, 1, 2, 3}).
tity: C(m + n, r) = C(m, r − k)C(n, k), when-
k = 0 A codeword is valid if and only if it contains an even
ever m, n, and r are nonnegative integers with r not ex- number of 0s and an even number of 1s. Let a n equal
ceeding either m or n.[Hint: Look at the coefficient of x r the number of valid codewords of length n. Furthermore,
n
m
in both sides of (1 + x) m+n = (1 + x) (1 + x) .]
letb n ,c n ,andd n equalthenumberofstringsofbase4dig-
44. This exercise shows how to use generating functions to its of length n with an even number of 0s and an odd num-
derive a formula for the sum of the first n squares. ber of 1s, with an odd number of 0s and an even number
2
a) Show that (x + x)/(1 − x) 4 is the gener- of 1s, and with an odd number of 0s and an odd number
ating function for the sequence {a n }, where of 1s, respectively.
2
2
2
n
a n = 1 + 2 + ··· + n . a) Show that d n = 4 − a n − b n − c n . Use this to show
n
b) Use part (a) to find an explicit formula for the sum that a n+1 = 2a n + b n + c n ,b n+1 = b n − c n + 4 ,
2
2
2
n
1 + 2 + ··· + n . and c n+1 = c n − b n + 4 .