Phase 19 - Lesson 19.6

Recurrence Relations and Generating Functions

From Fibonacci to Catalan: solving linear recurrences in closed form, and turning a whole sequence into a single analytic object you can manipulate.

⏱ 65 min● Advanced🔗 Prereqs: 19.5 combinatorics; Phase 2 series

↖ Phase 19 hub

Builds on: 19.5 counted directly; when direct counting fails, set up a recurrence.
Leads to: 19.7 evaluates recurrences by DP; 19.13 accelerates them with matrix powers; 19.11 uses generating functions for partitions. The Euler Lab’s Combinatorics path is full of ‘count the ways’ problems that yield to a recurrence.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Set up a recurrence from a combinatorial decomposition and verify it against brute force.
Solve a linear homogeneous recurrence with constant coefficients via the characteristic polynomial, including repeated roots.
Derive Binet’s formula for Fibonacci and explain why you should still not compute \(F_n\) with it in floating point.
Define the ordinary generating function of a sequence and use it to solve a recurrence and to extract coefficients.
Derive the Catalan numbers from a quadratic generating-function equation and interpret them combinatorially.

Key Vocabulary

Linear recurrence: \(a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}\) with constant \(c_i\); determined by \(k\) initial values.

Characteristic polynomial: \(x^k-c_1x^{k-1}-\cdots-c_k=0\); its roots \(r_i\) give the basis solutions \(r_i^n\) (times \(n^j\) for a root of multiplicity \(j+1\)).

Ordinary generating function (OGF): \(A(x)=\sum_{n\ge0}a_nx^n\): a formal power series that encodes the whole sequence as one object.

Convolution: \([x^n]A(x)B(x)=\sum_{k}a_kb_{n-k}\) - the algebraic shadow of ‘split the structure into two independent parts’.

Catalan number: \(C_n=\frac1{n+1}\binom{2n}{n}\): counts balanced bracketings, binary trees, monotone lattice paths below the diagonal, triangulations.

Golden ratio: \(\varphi=\frac{1+\sqrt5}{2}\approx1.618\): the dominant characteristic root of Fibonacci, so \(F_n\sim\varphi^n/\sqrt5\).

Intuition & Motivation

Intuition

A recurrence says how a structure of size n is built from smaller ones; that is a combinatorial statement first and an equation second. A generating function then packs the entire infinite sequence into one function, so that combinatorial operations (choose one of these OR one of those; concatenate an A and a B) become arithmetic (add; multiply). Once the operations are arithmetic, you can solve for the answer with algebra.

Setting up and solving linear recurrences

Fibonacci: \(F_n=F_{n-1}+F_{n-2}\), \(F_0=0,\ F_1=1\) - the number of ways to tile a \(1\times n\) strip with monominoes and dominoes, decomposed by what covers the last cell. That decomposition is the recurrence.

Theorem - Solution by characteristic roots

If the characteristic polynomial \(x^k=c_1x^{k-1}+\cdots+c_k\) has distinct roots \(r_1,\dots,r_k\), every solution is \(a_n=\sum_i \alpha_i r_i^n\) with the \(\alpha_i\) fixed by the initial conditions. A root \(r\) of multiplicity \(\mu\) contributes \(r^n,\ n r^n,\ \dots,\ n^{\mu-1}r^n\).

Worked Example - Binet’s formula

Characteristic equation: \(x^2=x+1\Rightarrow x^2-x-1=0\), roots \(\varphi=\frac{1+\sqrt5}{2},\ \psi=\frac{1-\sqrt5}{2}\) (note \(\psi=-1/\varphi\approx-0.618\)).

General solution \(F_n=\alpha\varphi^n+\beta\psi^n\). Impose \(F_0=0\Rightarrow\alpha+\beta=0\) and \(F_1=1\Rightarrow\alpha\varphi+\beta\psi=1\).

Then \(\alpha(\varphi-\psi)=1\) and \(\varphi-\psi=\sqrt5\), so \(\alpha=1/\sqrt5,\ \beta=-1/\sqrt5\).

\[F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\tfrac{1+\sqrt5}2,\ \psi=\tfrac{1-\sqrt5}2.\] (19.11)

Because \(|\psi|\lt 1\), \(F_n=\mathrm{round}(\varphi^n/\sqrt5)\) for all \(n\ge0\) - but in double precision this rounding is only trustworthy up to about \(n=70\), after which \(\varphi^n/\sqrt5\) exceeds \(2^{53}\) and the rounding is a coin flip (19.4).

Corollary (Lamé): the worst case of Euclid’s algorithm (19.1) is consecutive Fibonacci inputs, so the number of steps for inputs \(\lt N\) is at most \(\log_\varphi(\sqrt5 N)\approx4.785\log_{10}N+1.67\).

Key Idea

Closed forms are for understanding (growth rate, asymptotics, worst cases). For computing exact values, iterate the recurrence in integers, or use matrix exponentiation (19.13) when \(n\) is astronomically large.

Generating functions

Definition - Ordinary generating function

For a sequence \((a_n)_{n\ge0}\), \(A(x)=\sum_{n\ge0}a_nx^n\). We treat it formally: \(x\) is a bookkeeping symbol, and convergence is optional (though when the series does converge, analytic methods give asymptotics for free).

The mechanical method: multiply the recurrence by \(x^n\), sum over all \(n\) where it is valid, recognise shifted copies of \(A(x)\), and solve for \(A(x)\).

Worked Example - The Fibonacci OGF

Let \(F(x)=\sum_{n\ge0}F_nx^n\). Multiply \(F_n=F_{n-1}+F_{n-2}\) by \(x^n\) and sum over \(n\ge2\).

Left: \(F(x)-F_0-F_1x=F(x)-x\). Right: \(x\sum_{n\ge2}F_{n-1}x^{n-1}+x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x(F(x)-F_0)+x^2F(x)=xF(x)+x^2F(x)\).

So \(F(x)-x=(x+x^2)F(x)\), giving

\[F(x)=\frac{x}{1-x-x^2}.\] (19.12)

Partial fractions over the roots of \(1-x-x^2\) (which are \(1/\varphi\) and \(1/\psi\)) and expanding each \(\frac1{1-rx}=\sum r^nx^n\) recovers Binet (19.11) - the generating function derives the closed form rather than guessing it.

Bonus: reading off \([x^n]\) of \(\frac{x}{1-x-x^2}\) as a sum over compositions of \(n\) into 1s and 2s re-proves the tiling interpretation. One object, three viewpoints.

Catalan numbers: a nonlinear recurrence solved by a quadratic

Let \(C_n\) count binary trees with \(n\) internal nodes (equivalently, balanced bracket strings of length \(2n\)). Splitting a tree at its root into a left subtree with \(k\) nodes and a right subtree with \(n-1-k\) gives the convolution recurrence

\[C_0=1,\qquad C_{n}=\sum_{k=0}^{n-1}C_k\,C_{n-1-k}\ \ (n\ge1)\quad\Longrightarrow\quad C(x)=1+x\,C(x)^2 .\] (19.13)

Solving the quadratic and taking the branch with \(C(0)=1\): \(C(x)=\frac{1-\sqrt{1-4x}}{2x}\). Expanding \(\sqrt{1-4x}\) with the generalised binomial theorem yields

\[C_n=\frac{1}{n+1}\binom{2n}{n}:\qquad 1,1,2,5,14,42,132,429,\dots\] (19.14)

Note how the product \(C(x)^2\) encoded ‘a left subtree AND a right subtree’. That correspondence - disjoint union → sum, independent concatenation → product - is the whole reason generating functions work.

Coding workbench

Whenever a Euler Lab problem in the Combinatorics path says ‘in how many ways can …’ and the objects are built recursively (paths, trees, tilings, bracketings, coin decompositions), the intended route is: find the decomposition, write the recurrence, then either evaluate it by DP (19.7) or solve it in closed form here.

Common Mistakes to Avoid

Forgetting the initial conditions when writing the OGF equation - the \(-F_0-F_1x\) boundary terms are where most algebra errors live.
Using Binet in floating point for large \(n\) and trusting the digits. Beyond \(F_{78}\) a double cannot even hold the answer exactly (19.4).
Choosing the wrong branch of the quadratic in (19.13): \(\frac{1+\sqrt{1-4x}}{2x}\) blows up at \(x=0\) and is not a power series.
Assuming every recurrence has a nice closed form. Most do not; the recurrence itself, evaluated by DP, is often the final answer.
Mixing up \(O\)-growth with exact values: \(F_n\sim\varphi^n/\sqrt5\) tells you the answer has \(\approx0.209n\) digits, not what those digits are.

Quant Practitioner Tips

Always sanity-check a new recurrence by brute-force enumeration for \(n\le6\). A wrong recurrence run fast is still wrong.
‘Sum over a split point’ in a recurrence \(\Leftrightarrow\) ‘multiply the generating functions’. Recognising a convolution instantly is worth more than memorising the Catalan formula.
The dominant characteristic root gives the asymptotic growth for free, which is exactly what you need for the feasibility estimates of 19.14.
If the recurrence has constant coefficients and \(n\) is huge (\(10^{18}\)), stop - that is a matrix-power problem (19.13), and it runs in \(O(k^3\log n)\).

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#2 Even Fibonacci Numbers (1%, tier A) #6 Sum Square Difference (1%, tier A) #42 Coded Triangle Numbers (2%, tier A) #12 Highly Divisible Triangular Number (3%, tier A)

Applied:
#313 Sliding Game (16%, tier B) #816 Shortest Distance Among Points (17%, tier B) #323 Bitwise-OR Operations on Random In (18%, tier B)

Challenge:
#208 Robot Walks (41%, tier C) #375 Minimum of Subsequences (41%, tier C)

234 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Hard

The characteristic equation of \(a_n=4a_{n-1}-4a_{n-2}\) has a repeated root 2. The general solution is:

\(\alpha 2^n\)

\(\alpha2^n+\beta2^n\)

\(\alpha2^n+\beta n2^n\)

\(\alpha2^n+\beta(-2)^n\)

Q2 Medium

The generating function \(F(x)=x/(1-x-x^2)\) encodes Fibonacci because:

It converges for all x

Multiplying the recurrence by \(x^n\) and summing produces \(F(x)-x=(x+x^2)F(x)\)

Its derivative is \(F_n\)

It equals \(\varphi^n\)

Q3 Medium

You need \(F_{10^{18}}\bmod 10^9+7\). The right method is:

Binet in floating point

Iterate the recurrence \(10^{18}\) times

Matrix exponentiation of \(\begin{pmatrix}1&1\\1&0\end{pmatrix}\) by square-and-multiply

Precompute a table

Practical Exercise

(a) Solve \(a_n=5a_{n-1}-6a_{n-2}\) with \(a_0=1,\ a_1=4\) in closed form. (b) Find the OGF for the number of ways \(t_n\) to tile a \(1\times n\) strip with tiles of length 1 and 2, and identify the sequence. (c) Prove the Catalan convolution (19.13) combinatorially and use the OGF to get (19.14)’s first five values.

▶ Show full solution

(a) Characteristic: \(x^2-5x+6=0\Rightarrow x=2,3\) (distinct). So \(a_n=\alpha2^n+\beta3^n\). Initial conditions: \(\alpha+\beta=1\) and \(2\alpha+3\beta=4\), giving \(\beta=2,\ \alpha=-1\). Hence \(a_n=2\cdot3^n-2^n\). Check: \(a_0=2-1=1\) ✓, \(a_1=6-2=4\) ✓, \(a_2=18-4=14\) and \(5\cdot4-6\cdot1=14\) ✓.

(b) Decompose by the last tile: a length-1 tile leaves a strip of \(n-1\), a length-2 tile leaves \(n-2\). So \(t_n=t_{n-1}+t_{n-2}\) with \(t_0=1,\ t_1=1\). Summing against \(x^n\): \(T(x)-1-x=x(T(x)-1)+x^2T(x)\), so \(T(x)=\frac{1}{1-x-x^2}\). Comparing with (19.12), \(T(x)=F(x)/x\), i.e. \(t_n=F_{n+1}\) - the tilings ARE the Fibonacci numbers, shifted by one.

(c) A nonempty binary tree has a root; deleting it leaves an ordered pair (left subtree, right subtree) whose sizes sum to \(n-1\). Summing over the left size \(k\) gives \(C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}\), and the pair-of-independent-structures is exactly a product of OGFs, so \(C(x)=1+xC(x)^2\). Solving: \(xC^2-C+1=0\Rightarrow C=\frac{1\pm\sqrt{1-4x}}{2x}\); the \(+\) branch diverges as \(x\to0\), so take \(-\). Expanding: \(C(x)=1+x+2x^2+5x^3+14x^4+\cdots\), i.e. \(C_0..C_4=1,1,2,5,14\), matching \(\frac1{n+1}\binom{2n}{n}\) (\(\tfrac15\binom84=\tfrac{70}5=14\) ✓).

After the reveal, answer for yourself: In (b) you got Fibonacci from a completely different-looking problem. What structural feature of the two problems made them the same?

Lesson Summary

A recurrence is a combinatorial decomposition written as an equation. Linear constant-coefficient recurrences are solved by the characteristic polynomial (repeated roots contribute \(n^jr^n\)), giving Binet’s \(F_n=(\varphi^n-\psi^n)/\sqrt5\) and, with it, the growth rate and Euclid’s worst case. Generating functions package a whole sequence into one object so that ‘OR’ becomes addition and ‘AND/concatenate’ becomes multiplication - which is how the Catalan quadratic \(C=1+xC^2\) yields \(C_n=\frac1{n+1}\binom{2n}{n}\).

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: How do you solve a linear recurrence with a repeated characteristic root \(r\) of multiplicity \(\mu\)?
A: It contributes the \(\mu\) independent solutions \(r^n, nr^n, \dots, n^{\mu-1}r^n\); the coefficients are then fixed by the initial conditions.

Q: What combinatorial operation does multiplying two generating functions correspond to?
A: Convolution: choosing an A-structure and a B-structure whose sizes sum to \(n\) (\([x^n]AB=\sum_k a_kb_{n-k}\)). Disjoint union corresponds to addition.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. 10–11 (sequences & series) - Power series, formal manipulation, radius of convergence, and the binomial series \((1+x)^\alpha\) - exactly what is needed to expand \(\sqrt{1-4x}\) and extract \(C_n\).
Probability: Theory and Examples (Rick Durrett, 5th ed.) current - Ch. 4 (random walks) - Sequences of counts as distributions; the probabilistic reading of Catalan numbers via random walks conditioned to stay non-negative.
The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 7 - Validate a derived closed form against the brute-force recurrence for small \(n\) before trusting it at scale.

← 19.5 Next: 19.7 →