Generating Functions and the Binet Formula

Introduction

The Fibonacci sequence is one of mathematics’ most celebrated patterns: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34… Each number is simply the sum of the two preceding ones. This recursive definition is elegant and intuitive—so much so that it appears in Leonardo Fibonacci’s 1202 book Liber Abaci as a solution to a problem about breeding rabbits.

Fibonacci’s Rabbit Problem

The original problem Fibonacci posed was this: suppose you have a pair of baby rabbits. Each month:

Baby rabbits take one month to mature into adult rabbits
Adult rabbits produce one new pair of baby rabbits each month
Rabbits never die

How many pairs of rabbits will you have after$n$ months?

Let’s trace through the first few months:

Month 0: 1 pair of babies
Month 1: 1 pair of adults (the original babies grew up, but haven’t reproduced yet)
Month 2: 2 pairs total (1 adult pair + 1 new baby pair they produced)
Month 3: 3 pairs total (1 adult pair + 1 pair that just matured + 1 new baby pair)
Month 4: 5 pairs total (2 adult pairs + 2 baby pairs + 1 pair that just matured)

The key insight: at month$n$, the total population equals:

The population from month$n-1$ (all those rabbits are still alive)
Plus new babies born from adults that existed at month$n-2$ (since only rabbits that were adults last month can reproduce)

This gives us: $ F_n = F_{n-1} + F_{n-2} $

The adults from generation $n-2$ produce the baby generation, which joins the existing population from $n-1$ to give us the total at step $n$. It’s a beautiful biological model that naturally generates the recurrence relation:

$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ for } n \geq 2$$

But there’s something unsatisfying about this definition. Want to know the 100th Fibonacci number? You’ll need to compute all 99 numbers before it. There’s no shortcut—or is there?

Remarkably, there exists a closed-form formula that computes any Fibonacci number directly, without recursion. This formula, known as Binet’s formula after French mathematician Jacques Philippe Marie Binet, looks almost magical:

$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$

where $ \phi = \frac{1+\sqrt{5}}{2} $ (the golden ratio) and $ \psi = \frac{1-\sqrt{5}}{2} $.

How can a sequence defined by simple addition yield a formula involving irrational numbers and exponentials? The answer lies in one of mathematics’ most powerful tools: generating functions.

What Are Generating Functions?

The Core Idea

A generating function is a formal power series whose coefficients encode a sequence. For a sequence $ a_0, a_1, a_2, a_3, \ldots $, its generating function is:

$$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = \sum_{n=0}^{\infty} a_n x^n$$

At first glance, this seems like a strange thing to do. Why wrap a sequence in a power series? The magic lies in what happens when you manipulate these functions algebraically. Operations on generating functions correspond to operations on sequences, often in surprising and useful ways.

A Crucial Point: Convergence Is Optional

Here’s something that shocked 18th-century mathematicians: you don’t need the series to converge. Generating functions work as formal objects—algebraic expressions we manipulate according to rules, without worrying about whether they represent actual numerical values.

This was controversial when Euler and his contemporaries pioneered the technique. Today we understand that generating functions live in the ring of formal power series, where convergence is irrelevant. We’re doing algebra, not analysis.

As Herbert Wilf famously wrote: “A generating function is a clothesline on which we hang up a sequence of numbers for display.”

A Brief History of Generating Functions

The Early Pioneers: De Moivre and Euler

The story of generating functions begins in the early 18th century with Abraham de Moivre, a French mathematician who fled to England to escape religious persecution. In his 1730 work Miscellanea Analytica, de Moivre used generating functions to solve recurrence relations—exactly what we’ll do with Fibonacci numbers.

De Moivre’s motivation was probability theory. He wanted to compute the number of ways to achieve certain sums when rolling dice, problems that naturally led to recurrence relations. His insight was to encode these counting problems in power series and manipulate them algebraically.

Leonhard Euler, the most prolific mathematician in history, seized upon de Moivre’s ideas and expanded them dramatically. Euler used generating functions throughout his work on partition theory, number theory, and analysis. His fearless manipulation of infinite series—often without rigorous justification by modern standards—led to astonishing discoveries.

One famous example: Euler proved the beautiful identity

$$\prod_{n=1}^{\infty} (1 - x^n) = \sum_{k=-\infty}^{\infty} (-1)^k x^{k(3k-1)/2}$$

relating infinite products to infinite sums, using generating function techniques. This identity connects partition theory (counting ways to write integers as sums) with pentagonal numbers, a connection that seems to come from nowhere until you see the generating function proof.¹

Laplace’s Systematization

Pierre-Simon Laplace, working in the late 18th and early 19th centuries, brought generating functions to their mature form. In his masterwork Théorie Analytique des Probabilités (1812), Laplace systematically used what he called “generating functions” (fonctions génératrices) to solve probability problems.

Laplace’s key insight was that generating functions transform discrete problems (about sequences) into continuous problems (about functions). Differentiation, integration, and algebraic manipulation of functions could reveal properties of sequences that were difficult to see directly.

This was part of a broader program: using the power of calculus and analysis to solve discrete problems. The technique was so successful that it became standard in probability theory and eventually spread throughout mathematics.

A Delightful Anecdote: Euler’s Divergent Series

Euler’s relationship with convergence was, shall we say, relaxed. Consider his treatment of the series:

$$1 + 2 + 4 + 8 + 16 + \cdots$$

This series obviously diverges to infinity. But Euler noticed that if you treat it as a geometric series with ratio 2, the formula $ \frac{1}{1-r} $ gives $ \frac{1}{1-2} = -1 $.

So Euler declared: $ 1 + 2 + 4 + 8 + 16 + \cdots = -1 $.

Modern mathematicians recoiled at such statements, leading to the 19th-century rigorization of analysis. But Euler was onto something deep. In certain contexts (like 2-adic numbers or summation methods like Cesàro summation), this equation has rigorous meaning.

This exemplifies the generating function philosophy: manipulate formal expressions algebraically, and meaningful results emerge, even when classical convergence fails.

Finding Binet’s Formula

Now let’s use generating functions to discover the closed form for Fibonacci numbers. This derivation is a masterpiece of the technique—watch how algebraic manipulation transforms a recurrence relation into an explicit formula.

Step 1: Define the Generating Function

Let $ F(x) $ be the generating function for Fibonacci numbers:

$$F(x) = \sum_{n=0}^{\infty} F_n x^n = F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \cdots$$

Substituting the Fibonacci values:

$$F(x) = 0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + \cdots$$

Our goal: find a simple closed form for $ F(x) $, then extract the coefficient of $ x^n $ to get $ F_n $.

Step 2: Use the Recurrence Relation

The key insight: the recurrence relation $ F_n = F_{n-1} + F_{n-2} $ must be reflected in the generating function.

Multiply the recurrence by $ x^n $ and sum over all $ n \geq 2 $:

$$\sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n$$

The left side is almost $ F(x) $, just missing the first two terms:

$$F(x) - F_0 - F_1 x = F(x) - x$$

For the first term on the right, factor out$x$:

$$\sum_{n=2}^{\infty} F_{n-1} x^n = x \sum_{n=2}^{\infty} F_{n-1} x^{n-1} = x \sum_{m=1}^{\infty} F_m x^m = x(F(x) - F_0) = xF(x)$$

For the second term, factor out $ x^2 $:

$$\sum_{n=2}^{\infty} F_{n-2} x^n = x^2 \sum_{n=2}^{\infty} F_{n-2} x^{n-2} = x^2 \sum_{k=0}^{\infty} F_k x^k = x^2 F(x)$$

Putting it together:

$$F(x) - x = xF(x) + x^2 F(x)$$

Step 3: Solve for F(x)

Rearrange:

$$F(x) - xF(x) - x^2F(x) = x$$

$$F(x)(1 - x - x^2) = x$$

$$F(x) = \frac{x}{1 - x - x^2}$$

This is our generating function in closed form! But we need to extract the coefficient of $ x^n $.

Step 4: Partial Fractions

To find the coefficients, we use partial fraction decomposition. First, factor the denominator by finding roots of $ 1 - x - x^2 = 0 $, or equivalently, $ x^2 + x - 1 = 0 $:

$$x = \frac{-1 \pm \sqrt{5}}{2}$$

Let $ \phi = \frac{1 + \sqrt{5}}{2} $ (the golden ratio) and $ \psi = \frac{1 - \sqrt{5}}{2} $ (its conjugate).

Then the roots of $ 1 - x - x^2 $ are $ \alpha = \frac{1}{\phi} $ and $ \beta = \frac{1}{\psi} $.

Note: $ 1 - x - x^2 = -(x - \alpha)(x - \beta) = -(1 - x/\alpha)(1 - x/\beta) \cdot \alpha\beta $

After some algebra (noting that $ \alpha\beta = \frac{1}{\phi\psi} = -1 $ since $ \phi\psi = -1 $):

$$1 - x - x^2 = -(x - 1/\phi)(x - 1/\psi)$$

We can rewrite:

$$F(x) = \frac{x}{1 - x - x^2} = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \phi x} - \frac{1}{1 - \psi x} \right)$$

This partial fraction decomposition requires computing:

$$\frac{x}{(1 - \phi x)(1 - \psi x)} = \frac{A}{1 - \phi x} + \frac{B}{1 - \psi x}$$

Solving: $ x = A(1 - \psi x) + B(1 - \phi x) $

Setting $ x = 1/\phi $: $ 1/\phi = A(1 - \psi/\phi) = A(1 - \psi/\phi) $

Since $ \phi - \psi = \sqrt{5} $ and $ \phi\psi = -1 $:

$$A = \frac{1}{\phi(\phi - \psi)/\phi} = \frac{1}{\phi - \psi} = \frac{1}{\sqrt{5}}$$

Similarly, $ B = -\frac{1}{\sqrt{5}} $.

Therefore:

$$F(x) = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \phi x} - \frac{1}{1 - \psi x} \right)$$

Step 5: Extract Coefficients

Now we use the geometric series formula. Recall that:

$$\frac{1}{1 - r} = \sum_{n=0}^{\infty} r^n = 1 + r + r^2 + r^3 + \cdots$$

(This holds formally, regardless of convergence!)

Therefore:

$$\frac{1}{1 - \phi x} = \sum_{n=0}^{\infty} (\phi x)^n = \sum_{n=0}^{\infty} \phi^n x^n$$

$$\frac{1}{1 - \psi x} = \sum_{n=0}^{\infty} \psi^n x^n$$

So:

$$F(x) = \frac{1}{\sqrt{5}} \sum_{n=0}^{\infty} (\phi^n - \psi^n) x^n$$

The coefficient of $ x^n $ is:

$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$

This is Binet’s formula!

A Remarkable Observation

Notice something extraordinary: $ \psi = \frac{1-\sqrt{5}}{2} \approx -0.618 $, so $ |\psi| < 1 $. As$n$ grows, $ \psi^n $ becomes negligibly small.

This means:

$$F_n \approx \frac{\phi^n}{\sqrt{5}}$$

The Fibonacci numbers grow exponentially with rate $ \phi $, the golden ratio! And despite $ \phi $ being irrational, the formula always produces integers because the $ \psi^n $ term exactly cancels out the fractional part.

In fact, $ F_n $ is simply the nearest integer to $ \frac{\phi^n}{\sqrt{5}} $.

Why Generating Functions Work

The derivation above illustrates the power of generating functions:

Encoding: The sequence is encoded in the coefficients of a power series
Transformation: The recurrence relation becomes an algebraic equation
Solution: Algebra gives a closed form for the generating function
Extraction: Coefficient extraction reveals the closed form for the sequence

This technique works because generating functions transform discrete problems (recurrences) into continuous ones (functional equations). The tools of calculus and algebra then provide solutions that would be difficult to find directly.

Beyond Fibonacci: The Scope of Generating Functions

The Fibonacci example only scratches the surface. Generating functions solve countless problems in combinatorics, probability, number theory, and analysis:

Counting problems: How many ways can you make change for a dollar? How many binary trees have n nodes? Generating functions count them.
Probability: What’s the distribution of a sum of random variables? Generating functions (called moment generating functions or probability generating functions) make convolution trivial.
Asymptotic analysis: How does a sequence grow? Singularity analysis of generating functions reveals asymptotic behavior.
Identities: Prove combinatorial identities by showing two generating functions are equal.

Herbert Wilf’s book generatingfunctionology and Philippe Flajolet and Robert Sedgewick’s encyclopedic Analytic Combinatorics demonstrate the breathtaking scope of the technique.

Historical Footnote: Was Binet First?

Despite the name, Binet wasn’t the first to discover this formula. Abraham de Moivre derived it in 1730, a full century before Binet’s 1843 paper. Leonhard Euler and Daniel Bernoulli also knew the formula.

The misattribution likely occurred because Binet’s paper was widely read and cited. Mathematical history is full of such cases—Stigler’s law of eponymy states that “no scientific discovery is named after its original discoverer.”

The formula should perhaps be called de Moivre’s formula, but “Binet’s formula” has stuck. Such is the quirky nature of mathematical naming.

Conclusion

The journey from Fibonacci’s simple recurrence to Binet’s formula reveals a deep connection between the discrete and continuous, between recursion and closed form, between sequence and function. Generating functions provide the bridge.

What makes this technique so powerful is its generality. The same method that solved Fibonacci numbers solves countless other recurrences. It’s a hammer that sees many nails as generating functions, and remarkably, it works.

Perhaps most beautifully, generating functions remind us that convergence—that great preoccupation of 19th-century rigor—isn’t always necessary. Sometimes, as Euler knew, you can manipulate formal expressions fearlessly and trust the algebra to reveal truth.

The next time you encounter a sequence defined recursively, consider its generating function. You might be surprised what closed form emerges from the algebraic machinery—and you’ll be following in the footsteps of de Moivre, Euler, Laplace, and generations of mathematicians who discovered that clothing a sequence in a power series reveals its hidden structure.

Introduction#

Fibonacci’s Rabbit Problem#

What Are Generating Functions?#

The Core Idea#

A Crucial Point: Convergence Is Optional#

A Brief History of Generating Functions#

The Early Pioneers: De Moivre and Euler#

Laplace’s Systematization#

A Delightful Anecdote: Euler’s Divergent Series#

Finding Binet’s Formula#

Step 1: Define the Generating Function#

Step 2: Use the Recurrence Relation#

Step 3: Solve for F(x)#

Step 4: Partial Fractions#

Step 5: Extract Coefficients#

A Remarkable Observation#

Why Generating Functions Work#

Beyond Fibonacci: The Scope of Generating Functions#

Historical Footnote: Was Binet First?#

Conclusion#

Further Reading#