Page 570 - Discrete Mathematics and Its Applications

8.4 Generating Functions 549

Exercises

1. Find the generating function for the finite sequence 2, 2, 7. For each of these generating functions, provide a closed
2, 2, 2, 2. formula for the sequence it determines.
3
2. Find the generating function for the finite sequence 1, 4, a) (3x − 4) 3 b) (x + 1) 3
3
16, 64, 256. c) 1/(1 − 5x) d) x /(1 + 3x)
2
2
In Exercises 3–8, by a closed form we mean an algebraic ex- e) x + 3x + 7 + (1/(1 − x ))
4
3
4
2
pression not involving a summation over a range of values or f) (x /(1 − x )) − x − x − x − 1
2
the use of ellipses. g) x /(1 − x) 2 h) 2e 2x
3. Find a closed form for the generating function for each 8. For each of these generating functions, provide a closed
of these sequences. (For each sequence, use the most ob- formula for the sequence it determines.
2
vious choice of a sequence that follows the pattern of the a) (x + 1) 3 b) (3x − 1) 3
initial terms listed.) c) 1/(1 − 2x ) d) x /(1 − x) 3
2
2
3
a) 0, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, ... e) x − 1 + (1/(1 − 3x)) f) (1 + x )/(1 + x) 3
b) 0, 0, 0, 1, 1, 1, 1, 1, 1, ... ∗ g) x/(1 + x + x ) h) e 3x 2 − 1
2
c) 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ... 10
9. Find the coefficient of x in the power series of each of
d) 2, 4, 8, 16, 32, 64, 128, 256, ...
these functions.
7 7 7 7
e) , , ,..., ,0,0,0,0,0, ... a) (1 + x + x 10 + x 15 + ··· ) 3
5
0 1 2 7 3 4 5 6 7 3
f) 2, −2, 2, −2, 2, −2, 2, −2, ... b) (x + x + x + x + x + ··· ) 6 7
4
4
5
5
3
6
g) 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, ... c) (x + x + x )(x + x + x + x + x )(1 + x +
4
2
3
h) 0, 0, 0, 1, 2, 3, 4, ... x + x + x + ··· )
2 4 6 8 3 6 9
4. Find a closed form for the generating function for each d) (x + x + x + x + ··· )(x + x + x +
12
4
8
of these sequences. (Assume a general form for the terms ··· )(x + x + x + ··· ) 4 8 12
4
6
2
8
of the sequence, using the most obvious choice of such a e) (1 + x + x + x + x + ··· )(1 + x + x + x +
18
12
6
sequence.) ··· )(1 + x + x + x + ··· )
9
10. Find the coefficient of x in the power series of each of
a) −1, −1, −1, −1, −1, −1, −1, 0, 0, 0, 0, 0, 0, ...
b) 1, 3, 9, 27, 81, 243, 729, ... these functions. 6 9 3
3
c) 0, 0, 3, −3, 3, −3, 3, −3, ... a) (1 + x + x + x + ··· )
2
3
6
4
5
d) 1, 2, 1, 1, 1, 1, 1, 1, 1, ... b) (x + x + x + x + x + ··· ) 3
3 5 6 3 4 2 3 4
7 7 2 7 7 7 c) (x + x + x )(x + x )(x + x + x + x + ··· )
e) ,2 ,2 ,..., 2 ,0,0,0,0, ... 4 7 10 2 4 6 8
0 1 2 7 d) (x + x + x + x + ··· )(x + x + x + x +
f) −3, 3, −3, 3, −3, 3, ... ··· )
2 3
g) 0, 1, −2, 4, −8, 16, −32, 64, ... e) (1 + x + x )
h) 1, 0, 1, 0, 1, 0, 1, 0, ... 11. Find the coefficient of x 10 in the power series of each of
5. Find a closed form for the generating function for the these functions.
sequence {a n }, where a) 1/(1 − 2x) b) 1/(1 + x) 2
a) a n = 5 for all n = 0, 1, 2,.... c) 1/(1 − x) 3 d) 1/(1 + 2x) 4
n
4
b) a n = 3 for all n = 0, 1, 2,.... e) x /(1 − 3x) 3
c) a n = 2 for n = 3, 4, 5,... and a 0 = a 1 = a 2 = 0. 12. Find the coefficient of x 12 in the power series of each of
d) a n = 2n + 3 for all n = 0, 1, 2,.... these functions.

8 2
e) a n = for all n = 0, 1, 2,.... a) 1/(1 + 3x) b) 1/(1 − 2x)
n c) 1/(1 + x) 8 d) 1/(1 − 4x) 3
n + 4 3 2

f) a n = for all n = 0, 1, 2,.... e) x /(1 + 4x)
n
13. Use generating functions to determine the number of dif-
6. Find a closed form for the generating function for the ferent ways 10 identical balloons can be given to four
sequence {a n }, where children if each child receives at least two balloons.
a) a n =−1 for all n = 0, 1, 2,.... 14. Use generating functions to determine the number of dif-
n
b) a n = 2 for n = 1, 2, 3, 4,... and a 0 = 0. ferent ways 12 identical action figures can be given to five
c) a n = n − 1 for n = 0, 1, 2,.... children so that each child receives at most three action
d) a n = 1/(n + 1)! for n = 0, 1, 2,.... figures.

n
e) a n = for n = 0, 1, 2,.... 15. Use generating functions to determine the number of dif-
2
ferent ways 15 identical stuffed animals can be given to
10
f) a n = for n = 0, 1, 2,.... six children so that each child receives at least one but no
n + 1 more than three stuffed animals.