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

What is a Recurrence Relation?

Define recurrence relations as equations expressing terms in a sequence using previous terms, with examples like Fibonacci.

What is a Recurrence Relation?

What you'll learn: You'll discover how recurrence relations define sequences by expressing each term using previous terms rather than an explicit formula.

The Core Idea

A recurrence relation is an equation that defines a sequence by describing how to compute each term from one or more earlier terms in the sequence. Instead of giving you a direct formula like "the nth term equals 2n + 3," a recurrence relation says something like "the nth term equals the sum of the two previous terms."

Think of it like a recipe that tells you how to make today's batch of cookies using yesterday's leftover ingredients—you need the history to create what comes next.

Anatomy of a Recurrence Relation

A recurrence relation has two essential parts:

  1. The recursive formula: How to compute term(s) from previous term(s)
  2. Initial conditions: The first term(s) that get the sequence started

Without initial conditions, you can't actually compute the sequence—it's like having instructions without a starting point.

The Fibonacci Example

The most famous recurrence relation is the Fibonacci sequence:

  • Recurrence: F(n) = F(n-1) + F(n-2) for n ≥ 2
  • Initial conditions: F(0) = 0, F(1) = 1

This generates: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each term is the sum of the two preceding terms.

Other Examples

  • Arithmetic progression: a(n) = a(n-1) + d (constant difference)
  • Geometric progression: a(n) = r · a(n-1) (constant ratio)
  • Factorial: n! = n · (n-1)! with 0! = 1

Recurrence relations appear naturally in counting problems, algorithm analysis, probability, and modeling processes that depend on previous states.

Key Takeaway: A recurrence relation defines a sequence recursively by expressing each term as a function of earlier terms, combined with initial conditions that anchor the sequence.