Linear recurrence relations

A recurrence relation describes a sequence by how each term depends on the ones before: a loan balance after each repayment, a population after each breeding season, the number of valid strings of each length. Solving it means finding a formula for uₙ directly. This lesson solves first-order relations by measuring each term from the fixed point, solves second-order relations with a characteristic equation (distinct, repeated and complex roots), and sets up a second-order model from a counting argument.

First-order relations move towards or away from a fixed point

Consider uₙ = auₙ₋₁ + b with constants a ≠ 0 and b. If a ≠ 1, the fixed point L satisfies L = aL + b, so L = b/(1-a). Subtracting L = aL + b from the relation gives

The distance from the fixed point is multiplied by a at every step, so the long-term behaviour depends on a (when u₀ ≠ L):

If a = 1 the relation is arithmetic: uₙ = u₀ + nb. If u₀ = L, the sequence stays at L for every a.

Save example

Worked example 1

Paying off a loan

A loan of $20 000 has interest of 1% added at the end of each month, after which $500 is repaid. Let Bₙ be the balance in dollars after n months. Find Bₙ and the number of monthly payments needed to clear the loan.

Show full solutionHide solution

1. Write the recurrence

   Method

   Each month multiplies the balance by 1.01 and then subtracts 500.

   Reason

   The order of interest and repayment fixes the constants.

   Working

   Answer

   Bₙ = 1.01Bₙ₋₁-500, with B₀ = 20000.

2. Solve with the fixed point

   Method

   L = (-500)/(1-1.01) = 50000.

   Reason

   Here a = 1.01 > 1, so the balance moves away from 50000; starting below it, it falls.

   Working

   Answer

   Bₙ = 50000 + (20000-50000)(1.01)ⁿ = 50000-30000(1.01)ⁿ.

3. Find when the balance is cleared

   Method

   Solve Bₙ ≤ 0.

   Reason

   n counts whole payments, so take the least integer that works.

   Working

   Answer

   (1.01)ⁿ ≥ 5/3, so n ≥ (ln(5/3))/(ln 1.01) ≈ 51.34. The loan is cleared by the 52nd payment, which is smaller than $500.

Quick check

B₁ = 1.01 × 20000-500 = 19700, and the formula gives 50000-30300 = 19700. If the repayment were $200 instead, L = 20000 = B₀ and the balance would never fall: interest would exactly cancel each payment.

Check your understanding 1

Use the fixed point

The sequence uₙ satisfies uₙ = 3uₙ₋₁-2 with u₀ = 5. Find uₙ in terms of n, and hence u₃.

u₃

Check

Show answerHide answer

The fixed point solves L = 3L-2, so L = 1, and uₙ-1 is multiplied by 3 at each step:

uₙ = 1 + (5-1)3ⁿ = 1 + 4 · 3ⁿ, u₃ = 1 + 4 · 27 = 109.

Generating terms checks this: u₁ = 13, u₂ = 37, u₃ = 109. Because the multiplier 3 exceeds 1, the terms move away from the fixed point.

Second-order relations use a characteristic equation

For uₙ = puₙ₋₁ + quₙ₋₂ with constants p and q ≠ 0, try uₙ = λⁿ. Dividing by λⁿ⁻² gives the characteristic equation λ² = pλ + q. As with differential equations, linearity lets solutions be combined, and the two starting terms fix two constants.

The complex case comes from de Moivre’s theorem: (ρ e^(± iθ))ⁿ = ρⁿe^(± inθ).

For example, uₙ = uₙ₋₁ + 6uₙ₋₂ with u₀ = 1, u₁ = 8 has λ²-λ-6 = (λ-3)(λ + 2) = 0. So uₙ = A 3ⁿ + B(-2)ⁿ, with A + B = 1 and 3A-2B = 8. Then A = 2, B = -1, and uₙ = 2 · 3ⁿ-(-2)ⁿ. Check: the relation gives u₂ = 8 + 6 = 14, and the formula gives 18-4 = 14.

Check your understanding 2

Repeated and complex roots

1. Solve uₙ = 4uₙ₋₁-4uₙ₋₂ with u₀ = 1, u₁ = 4.
2. Solve uₙ = -uₙ₋₂ with u₀ = 2, u₁ = 0, and describe the sequence.

Both general terms and your description

Show answerHide answer

1. λ²-4λ + 4 = (λ-2)², so uₙ = (A + Bn)2ⁿ. Then A = 1 and 2(1 + B) = 4, so B = 1: uₙ = (n + 1)2ⁿ. Check u₂ = 16-4 = 12 = 3 × 4.
2. λ² + 1 = 0 gives λ = ± i = cos π/2± i sin π/2, so uₙ = C cos nπ/2 + D sin nπ/2. Then C = 2 and D = 0: uₙ = 2 cos nπ/2, the repeating pattern 2,0,-2,0,…, which never converges.

Modelling with a second-order relation

Common mistakes

• Writing uₙ = aⁿu₀ for uₙ = auₙ₋₁ + b, which ignores the constant b.
• Using u₁ as the starting value when the sequence is indexed from u₀, or the reverse.
• For a repeated root α, writing Aαⁿ + Bαⁿ instead of (A + Bn)αⁿ.
• Finding the constants from the first two terms of the wrong index.
• Setting up a modelling recurrence without checking it against the first few cases counted directly.

Before you move on

Save example

Try it yourself 1

Strings with no two adjacent 1s

Minimal support

Let aₙ be the number of strings of n binary digits with no two adjacent 1s. Show that aₙ = aₙ₋₁ + aₙ₋₂ for n ≥ 3, find a₁₀, and find the limit of aₙ₊₁/aₙ.

Write your answer, then compare it with the solution

Your argument for the recurrence, a₁₀ and the limit

Hint 1

Look at the last digit

A valid string ending in 0 can have any valid string before it. A valid string ending in 1 must have 0 just before that 1.

Show full solutionHide solution

1. Count by the last digit

   Method

   Split the valid strings of length n by their last digit.

   Reason

   Each class is in one-to-one correspondence with shorter valid strings.

   Working

   Answer

   Ending in 0: remove it to get any valid string of length n-1, so there are aₙ₋₁. Ending in 1: the string ends 01, and removing those two digits gives any valid string of length n-2, so there are aₙ₋₂. Hence aₙ = aₙ₋₁ + aₙ₋₂.

2. Start and iterate

   Method

   a₁ = 2 (0, 1) and a₂ = 3 (00, 01, 10).

   Reason

   The step from length 2 uses lengths 1 and 0 only through these two counts.

   Working

   Answer

   2,3,5,8,13,21,34,55,89,144, so a₁₀ = 144.

3. Find the limiting ratio

   Method

   The characteristic equation λ² = λ + 1 has roots φ = (1 + square root of 5)/2 and ψ = (1- square root of 5)/2.

   Reason

   |ψ| < 1, so the ψⁿ term vanishes relative to the φⁿ term.

   Working

   Answer

   aₙ = Aφⁿ + Bψⁿ with A ≠ 0 (the terms grow), so

   aₙ₊₁/aₙ → φ = (1 + square root of 5)/2 ≈ 1.618.

Quick check

Listing all 8 strings of length 3 leaves 5 valid ones (000, 001, 010, 100, 101), matching a₃ = a₂ + a₁. 144/89 ≈ 1.6180 already agrees with φ to four decimal places. Compare your explanation of the recurrence with the solution; it is self-checked.

Relations that need a given substitution to become linear are taught in Recurrences solved by substitution.