Skip to main content

What is a recurrence relation

Short answer

A recurrence relation expresses a_n in terms of previous terms a_{n-1}, a_{n-2}, ... for n ≥ n0. Initial conditions specify the first few terms to determine a unique solution. Example: Fibonacci f_n = f_{n-1} + f_{n-2}, f_0=0, f_1=1. Solving yields a closed form.

What do you understand by recurrence relation? Explain in brief.

A recurrence relation for a sequence {aₙ} is an equation that expresses aₙ in terms of one or more of the earlier terms a₀, a₁, ..., aₙ₋₁, for all n ≥ n₀. A sequence is called a solution if its terms satisfy the relation. The initial conditions specify the first few terms and fix a unique solution.

Examples:

  • Fibonacci: fₙ = fₙ₋₁ + fₙ₋₂, with f₀ = 0, f₁ = 1 gives 0, 1, 1, 2, 3, 5, 8, ...
  • aₙ = 2aₙ₋₁ + 1 with a₁ = 1 gives 1, 3, 7, 15, ... whose solution is aₙ = 2ⁿ − 1 (the Tower of Hanoi moves).

Key points:

  • The order (degree) is the difference between the largest and smallest subscripts, so the Fibonacci relation is of order 2.
  • A recurrence is linear if aₙ appears only to the first power, and with constant coefficients if the multipliers are constants.
  • To solve one means to find a closed formula for aₙ, by iteration (backward substitution) or by the characteristic-equation method for linear relations.
  • Applications: counting problems, analysis of the running time of recursive algorithms (such as binary search, T(n) = T(n/2) + 1), compound interest, population models.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 3 questions →