Skip to main content

Linear homogeneous and non-homogeneous recurrence

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.

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

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.
RelationTypeReason
aₙ = 3aₙ₋₁linear homogeneous, order 1no extra term
aₙ = 2aₙ₋₁ + 2n²linear non-homogeneousF(n) = 2n²
aₙ = aₙ₋₁² + aₙ₋₂not linearaₙ₋₁ squared
aₙ = n·aₙ₋₁linear homogeneous but not constant coefficientsmultiplier n

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 3 questions →