What is the generating function G(z) for the sequence of Fibonacci numbers F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, ...?

GATE 1987 · Discrete Mathematics · Generating Functions · medium

Answer: G(z) = z / (1 - z - z^2)

1. Set up the sum from the recurrence: G(z) = sum_{n>=0} F_n z^n = F_0 + F_1 z + sum_{n>=2} F_n z^n = 0 + z + sum_{n>=2} (F_{n-1} + F_{n-2}) z^n.
2. Express each shifted sum in terms of G(z): sum_{n>=2} F_{n-1} z^n = z * sum_{n>=2} F_{n-1} z^{n-1} = z * G(z) (since F_0 = 0 means the n=1 term contributes 0). Similarly sum_{n>=2} F_{n-2} z^n = z^2 * G(z). So G(z) = z + z*G(z) + z^2*G(z).
3. Solve for G(z): G(z)(1 - z - z^2) = z, so G(z) = z / (1 - z - z^2).