Recurrence relations · Grade 12

In Grade 12 you learn: recurrence relations.

A recurrence relation defines each term of a sequence from the ones before it. Examples are “add interest, then add a deposit” or “each pair of rabbits produces another pair”. Solving one gives a formula for the nth term, so you can jump straight to the 100th term.

Key facts

• First order uₙ₊₁ = auₙ + b (a ≠ 1): the fixed point is L = b/(1 − a) and the solution is uₙ = a^n(u₀ − L) + L.
• It converges to L exactly when |a| < 1 (unless it starts at L).
• Second order uₙ₊₂ = puₙ₊₁ + quₙ: the auxiliary equation is r^2 = pr + q.
• Distinct roots α and β: uₙ = Aαⁿ + Bβⁿ. A repeated root α: uₙ = (A + Bn)αⁿ. Use the first two terms to find A and B.
• Arithmetic (uₙ₊₁ = uₙ + d) and geometric (uₙ₊₁ = ruₙ) sequences are the simplest recurrences.
• Counting problems give recurrences: climbing stairs 1 or 2 at a time gives the Fibonacci numbers.