---
title: "What is a recurrence relation"
subject: "Discrete Structure"
chapter: 3
key: "semester_4/discrete_structure:recurrence-relation-definition"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/recurrence-relation-definition
site: BCT Engineering
---

# What is a recurrence relation

Discrete Structure · Chapter 3: Recurrence Relation

- Asked in: 2073 Magh, 3 marks; 2070 Bhadra, 2 marks (asked 2 times)
- Video: [Introduction to Recurrence Relations || Definition || Example || Fibonacci Sequence || DMS || MFCS](https://www.youtube.com/watch?v=UwZCaqLjpYs) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/recurrence-relation-definition
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-3

## Question

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

## 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.

## Answer

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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a recurrence relation?
   A. An equation giving a_n only in terms of n
   B. A list of the first terms
   C. An equation expressing a_n in terms of earlier terms of the sequence
   D. A formula for the sum of terms
   Answer: C. It relates a_n to a_(n-1), a_(n-2), ... (Key point: Definition)

2. What is the role of initial conditions?
   A. They give the order
   B. They make the relation linear
   C. They give the characteristic equation
   D. They fix one unique solution of the recurrence
   Answer: D. Without them a recurrence has infinitely many solutions. (Key point: Initial conditions)

3. What is the order of f_n = f_(n-1) + f_(n-2)?
   A. 2
   B. 1
   C. 3
   D. 0
   Answer: A. Largest minus smallest subscript is n − (n−2) = 2. (Key point: Order)

4. a_n = 2a_(n-1) + 1 with a_1 = 1 has which solution?
   A. a_n = 2^n
   B. a_n = 2^n − 1
   C. a_n = n^2
   D. a_n = 2n − 1
   Answer: B. Values 1, 3, 7, 15 match 2^n − 1. (Key point: Tower of Hanoi solution)

## Related in Discrete Structure

- [Solve third-order recurrence with n·4ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-third-order-n-4-power-n) — Discrete Structure, chapter 3, asked 6×
- [Linear homogeneous and non-homogeneous recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alinear-homogeneous-nonhomogeneous-recurrence) — Discrete Structure, chapter 3
- [Set up recurrence for Tower of Hanoi](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-setup-recurrence) — Discrete Structure, chapter 3
- [Derive and solve Tower of Hanoi recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-derive-and-solve) — Discrete Structure, chapter 3

## Related in other subjects

- [Engineer's relation with client, contractor, fellows](https://www.bctengineer.com/question.md?key=semester_8%2Fengineering_professional_practice%3Aengineer-relation-client-contractor) — Engineering Professional Practice, chapter 3