---
title: "Linear homogeneous and non-homogeneous recurrence"
subject: "Discrete Structure"
chapter: 3
key: "semester_4/discrete_structure:linear-homogeneous-nonhomogeneous-recurrence"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/linear-homogeneous-nonhomogeneous-recurrence
site: BCT Engineering
---

# Linear homogeneous and non-homogeneous recurrence

Discrete Structure · Chapter 3: Recurrence Relation

- Asked in: 2074 Bhadra, 3 marks
- Video: [[Discrete Mathematics] Nonhomogeneous Recurrence Relation Examples](https://www.youtube.com/watch?v=UVuSLfdcT_Y) — TrevTutor
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/linear-homogeneous-nonhomogeneous-recurrence
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-3

## Question

State linear homogeneous and non-homogeneous recurrence relation with examples.

## Short answer

Linear homogeneous: a_n = c1 a_{n-1} + ... + ck a_{n-k}, no extra term. Example: a_n = 5a_{n-1} - 6a_{n-2}. Non-homogeneous: includes a function F(n) ≠ 0. Example: a_n = 2a_{n-1} + 3^n. Solution is homogeneous solution plus particular solution.

## Answer

A **linear recurrence relation with constant coefficients of order k** has the form

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ + F(n),

where c₁, ..., cₖ are real constants and cₖ ≠ 0.

- **Linear homogeneous:** F(n) = 0, so every term is a multiple of an earlier term.
  Examples: aₙ = 5aₙ₋₁ − 6aₙ₋₂; Fibonacci fₙ = fₙ₋₁ + fₙ₋₂.
  Solved with the characteristic equation rᵏ − c₁rᵏ⁻¹ − ... − cₖ = 0.
- **Linear non-homogeneous:** F(n) ≠ 0 is a function of n only.
  Examples: aₙ = 2aₙ₋₁ + 3ⁿ; aₙ = aₙ₋₁ + n (F(n) = n); Hanoi: Hₙ = 2Hₙ₋₁ + 1.
  The solution is aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾, a homogeneous solution plus any particular solution.

| Relation | Type | Reason |
|---|---|---|
| aₙ = 3aₙ₋₁ | linear homogeneous, order 1 | no extra term |
| aₙ = 2aₙ₋₁ + 2n² | linear non-homogeneous | F(n) = 2n² |
| aₙ = aₙ₋₁² + aₙ₋₂ | not linear | aₙ₋₁ squared |
| aₙ = n·aₙ₋₁ | linear homogeneous but not constant coefficients | multiplier n |

## Check yourself

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

1. When is a linear recurrence homogeneous?
   A. F(n) is a constant
   B. F(n) is a polynomial
   C. All coefficients are 1
   D. F(n) = 0
   Answer: D. There is no extra term depending only on n. (Key point: Homogeneous)

2. Which relation is not linear?
   A. a_n = a_(n-1)^2 + a_(n-2)
   B. a_n = 3a_(n-1)
   C. a_n = 2a_(n-1) + 2n^2
   D. a_n = n·a_(n-1)
   Answer: A. a_(n-1) appears squared. (Key point: Non-linear example)

3. Why is a_n = n·a_(n-1) not with constant coefficients?
   A. It is not homogeneous
   B. It is non-linear
   C. The multiplier n is not a constant
   D. It has order 2
   Answer: C. It is linear homogeneous, but the coefficient depends on n. (Key point: Non-constant coefficients)

4. How is a non-homogeneous solution written?
   A. a_n = homogeneous × particular
   B. a_n = particular only
   C. a_n = F(n) + a_(n-1)
   D. a_n = homogeneous solution + a particular solution
   Answer: D. The general solution is the sum. (Key point: Solution structure)

## Related in Discrete Structure

- [What is a recurrence relation](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-relation-definition) — Discrete Structure, chapter 3, asked 2×
- [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×
- [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

- [Linear and non-linear behaviour of structures](https://www.bctengineer.com/question.md?key=semester_4%2Ftheory_of_structures_i%3Alinear-nonlinear-behaviour) — Theory of Structures I, chapter 1, asked 3×
- [What is a stack; linear or non-linear](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-linear-or-nonlinear) — Data Structure and Algorithm, chapter 2
- [Non-linear effect in FDMA; channels numerical](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Afdma-nonlinear-channels) — Wireless Communication, chapter 7
- [Analog and digital system block diagrams; linear and non-linear distortion](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aanalog-digital-block-linear-nonlinear-distortion) — Communication Systems, chapter 1