Recurrence Relations

A recurrence relation defines each term of a sequence in terms of earlier terms, and generating functions provide a systematic route to closed-form solutions.

Definition

A recurrence relation is an equation expressing each term of a sequence as a function of one or more preceding terms together with initial conditions that determine the sequence uniquely.

Scope

This topic covers linear recurrences with constant coefficients and their characteristic-equation solutions, the Fibonacci and Catalan recurrences, divide-and-conquer recurrences, and the generating-function method that converts a recurrence into an algebraic equation. It bridges elementary counting and the analytic study of growth rates.

Core questions

• How is a sequence defined recursively from earlier terms and initial values?
• How does the characteristic equation solve a linear recurrence with constant coefficients?
• How do generating functions convert a recurrence into a solvable algebraic equation?
• How do divide-and-conquer recurrences describe algorithm running times?

Key concepts

• Linear recurrence with constant coefficients
• Characteristic equation
• Fibonacci numbers
• Catalan numbers
• Divide-and-conquer recurrences
• Generating-function solution

Key theories

Characteristic-equation method

A linear recurrence with constant coefficients is solved by finding the roots of its characteristic polynomial; the general solution is a combination of exponential terms determined by those roots and the initial conditions.

Generating-function solution

Multiplying a recurrence by a formal variable and summing turns it into an algebraic equation for the generating function, whose expansion yields a closed form for the sequence, as for the Catalan and Fibonacci numbers.

Clinical relevance

Recurrence relations describe the running time of recursive algorithms, where divide-and-conquer recurrences and the master theorem give complexity bounds, and they model discrete dynamical and population processes.

History

Fibonacci's 13th-century rabbit problem gave the archetypal recurrence; de Moivre and Euler developed generating-function and characteristic-root methods that remain the standard solution techniques.

Key figures

• Leonardo of Pisa (Fibonacci)
• Abraham de Moivre
• Eugene Catalan

Seminal works

• stanley2011

Frequently asked questions

What are the Catalan numbers?

The Catalan numbers count many combinatorial objects - balanced parentheses, triangulations, binary trees - and satisfy a quadratic recurrence solvable by generating functions to give a closed binomial form.

Why use generating functions to solve recurrences?

They convert an infinite family of recursive equations into a single algebraic equation, from which a closed-form expression for every term can be extracted at once.