Course contentsShow
← Mathematics
Lesson 2644 of 3,12152. CombinatoricsFree lesson

The Generating Function for Fibonacci Numbers

Derive the closed-form generating function for the Fibonacci sequence as a worked example.

The Generating Function for Fibonacci Numbers

You'll learn: How to derive a closed-form expression for the generating function of the Fibonacci sequence using algebraic manipulation.

The Core Idea

The Fibonacci numbers are defined by F₀ = 0, F₁ = 1, and Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2. Instead of computing each term recursively, we can encode the entire sequence into a single function G(x) = F₀ + F₁x + F₂x² + F₃x³ + ⋯ and find a simple formula for it.

Deriving the Generating Function

Let G(x) = Σ Fₙxⁿ (sum from n=0 to ∞).

Step 1: Write out what we know:

  • G(x) = F₀ + F₁x + F₂x² + F₃x³ + ⋯
  • xG(x) = F₀x + F₁x² + F₂x³ + ⋯
  • x²G(x) = F₀x² + F₁x³ + ⋯

Step 2: Use the recurrence relation Fₙ = Fₙ₋₁ + Fₙ₋₂. This means:

G(x) − xG(x) − x²G(x) = F₀ + (F₁ − F₀)x + (F₂ − F₁ − F₀)x² + ⋯

Since F₀ = 0, F₁ = 1, and every later term Fₙ − Fₙ₋₁ − Fₙ₋₂ = 0 by the recurrence:

G(x)(1 − x − x²) = 0 + 1·x = x

Step 3: Solve for G(x):

G(x) = x/(1 − x − x²)

This compact formula encodes all Fibonacci numbers! Think of it as compressing an infinite list into a single algebraic expression.

Why This Matters

This closed form allows us to extract Fibonacci numbers using partial fractions or power series expansion—techniques that often reveal patterns invisible in the recursive definition.

Key Takeaway: The generating function for the Fibonacci sequence is G(x) = x/(1 − x − x²), derived by leveraging the recurrence relation to eliminate all but the initial terms.