ABSTRACT
Given any sequence a0, a1, a2, . . . , we define the (ordinary) generating function
f(x) =
anx n = a0 + a1x+ a2x
2 + a3x 3 + · · · .
The infinite series may or may not converge.
Example 7.1. Find the ordinary generating function for the Fibonacci sequence {F0, F1, F2, . . .}. Solution: Let f(x) =
∑∞ n=0 Fnx
n. Then
f(x) = x+ x2 + 2x3 + 3x4 + 5x5 + · · · xf(x) = x2 + x3 + 2x4 + 3x5 + 5x6 + · · · x2f(x) = x3 + x4 + 2x5 + 3x6 + 5x7 + · · · .
