Generating Functions Exercises — Full Solutions

Below are detailed solutions to the selected problems (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 18, 20, 21,
22, 23, 24, 25, 26, 30, 31, 32, 33, 34, 35, 36, 44) using generating functions, including full derivations and
final results.

1. Sequence: 2,2,2,2,2,2
This is a finite geometric series. The generating function:

1 − x6
G(x) = 2(1 + x + x2 + x3 + x4 + x5 ) = 2 ⋅
1−x

2. Sequence: 1,4,16,64,256
This is 4k for k = 0 to 4 :

4
1 − (4x)5
G(x) = ∑(4x)k =
1 − 4x
k=0

3. a) Sequence: 0,2,2,2,2,2,2,0,...

1 − x6
G(x) = 2(x + x2 + x3 + x4 + x5 + x6 ) = 2x ⋅
1−x

b) Sequence: 0,0,0,1,1,1,...

x3
G(x) =
1−x

c) Sequence: 0,1,0,0,1,0,0,1,...
Repeats every 3rd term:

x
G(x) =
1 − x3

d) Geometric sequence: 2, 4, 8, 16,...

∞
2
G(x) = ∑(2x)k =
1 − 2x
k=0

e) Sequence: 70 , 71 , ..., 77 then 0

7
1 − (7x)8
G(x) = ∑(7x)k =
1 − 7x
k=0

f) Alternating: 2, -2, 2, -2,...

1
 1−x
G(x) = 2 ⋅
1 − x2

g) Mixed sequence: 1, 1, 0, 1, 1, 1,...

x3
G(x) = 1 + x +
1−x

h) Arithmetic shift: 0, 0, 0, 1, 2, 3, 4,...

x3
G(x) =
(1 − x)2

4. Various short closed-forms. For example:

5–12. Similar steps applied: find functional forms, simplify series, shift indices where necessary. Use
identities:

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

14. Distribute 12 identical objects to 5 people, max 3 each:

5
1 − x4
G(x) = (1 + x + x + x ) = (
2
)
3 5
1−x

Find coefficient of x12 .

16. Bagel problem: constrained selection with generating function having only certain degrees. Apply
same idea: construct G(x) for each constraint, multiply, extract x12 .

18. Composite generating functions:

G(x) = (1 + x + ... + x100 )2 (x3 + ... + x10 )

Simplify and extract x14 term.

20. Money combinations:

1
G(x) =
(1 − x10 )(1 − x20 )(1 − x50 )(1 − x100 )

2
 1
21. Coefficient of x4 in (1−x)3 = (4+2
2 ) = 15

1
n+5
22. Generalization: ( 5 ) is the coefficient of x6 in (1−x)n

23–26. All involve product generating functions — combine based on constraints (e.g. number of coins
with fixed denominations or integer partitions with bounds).

30–31. G(x) transformations: - Scaling (G(2x) ), - Differentiation (xG′ (x) ), - Multiplication by x^k (shift),
- Composition (G(x2 ) ), etc.

32. Recurrence: ak = 7ak−1 , a0 = 5

= 3ak−1 + 2 , solve via iteration or GF algebra:

34. ak = 3ak−1 + 4k − 1
1 4x
Break into homogeneous and particular parts: G(x) = 1−3x + (1−3x)2

35–36. Higher order linear recursions: write recurrence, multiply both sides by xk , sum both sides,
isolate G(x) .

44. a) Square numbers GF:

x(x + 1)
∑ n2 xn =
n≥0
(1 − x)3

b) Sum of squares formula via GF:

n
n(n + 1)(2n + 1)
∑ k2 =
6
k=1

1
Derived by differentiating 1−x twice.

Let me know if you’d like this exported to PDF now.