On this page
A recurrence relation gives each term of a sequence from the terms before it, instead of giving a direct formula for the nth term. NCERT's Class 11 chapter on sequences uses the idea twice: it defines the Fibonacci sequence by the recurrence a₁ = a₂ = 1, aₙ = aₙ₋₂ + aₙ₋₁, and its Example 3 builds 1, 3, 5, 7, 9 from a₁ = 1, aₙ = aₙ₋₁ + 2 (NCERT Class 11 Mathematics, Chapter 8: Sequences and Series). JEE and olympiad questions give you the rule and ask for a₁₀₀, a closed formula or a limit.
How do you find the nth term of aₙ = p·aₙ₋₁ + q?
Look at p first. If p = 1, the rule just adds q each time, so the sequence is an AP: aₙ = a₁ + (n − 1)q.
If p ≠ 1, find the fixed point: the value L that the rule leaves unchanged. Solve L = pL + q, which gives L = q/(1 − p).
Subtract L = pL + q from aₙ = p·aₙ₋₁ + q to get aₙ − L = p(aₙ₋₁ − L). So bₙ = aₙ − L is a GP with common ratio p.
Write the answer: aₙ = L + (a₁ − L)·pⁿ⁻¹.
Check n = 1, 2 and 3 against the original rule before you move on.
Worked example: how many moves does the Tower of Hanoi need?
To move n discs, shift the top n − 1 to the spare peg, move the largest, then put the n − 1 back on top. So the move count obeys aₙ = 2aₙ₋₁ + 1, with a₁ = 1.
Here p = 2 and q = 1, so L = 1/(1 − 2) = −1. The rule becomes aₙ + 1 = 2(aₙ₋₁ + 1). The sequence aₙ + 1 is a GP that starts at 2 with ratio 2, so aₙ + 1 = 2ⁿ, which means aₙ = 2ⁿ − 1.
The OEIS entry for 2ⁿ − 1 lists this same recurrence, a(n+1) = 2a(n) + 1, and gives it as the minimum number of moves for the disc puzzle (OEIS A000225). For the puzzle itself, read our post on the Tower of Hanoi move pattern.
Two more to try:
a₁ = 5, aₙ = 3aₙ₋₁ − 4. L = −4/(1 − 3) = 2, so aₙ = 2 + 3·3ⁿ⁻¹ = 2 + 3ⁿ. Check: 5, 11, 29.
a₁ = 0, aₙ = aₙ₋₁/2 + 3. L = 3/(1 − 1/2) = 6, so aₙ = 6 − 6·(1/2)ⁿ⁻¹. The terms 0, 3, 4.5, 5.25 creep up towards 6. Because p lies between −1 and 1, the term (a₁ − L)·pⁿ⁻¹ shrinks to zero and aₙ tends to L, as the diagram at the top shows.
How do you prove a pattern you have spotted?
Sometimes you write out 1, 3, 7, 15 and guess 2ⁿ − 1. A guess earns no marks in a "show that" question; induction turns it into a proof.
Base case: a₁ = 2¹ − 1 = 1, which matches.
Inductive step: assume aₖ = 2ᵏ − 1. Then aₖ₊₁ = 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1.
Conclusion: the formula holds for every n ≥ 1.
The fixed-point method is already a proof, so save induction for guessed formulas. For setting it out in full, see how proof by mathematical induction works.
What changes in olympiad-style recurrences?
Harder problems disguise the same idea in three common ways.
Reciprocal substitution. For aₙ₊₁ = aₙ/(1 + aₙ), put bₙ = 1/aₙ. Then bₙ₊₁ = (1 + aₙ)/aₙ = bₙ + 1, an AP. With a₁ = 1 you get bₙ = n, so aₙ = 1/n.
A term that depends on n. For aₙ = 2aₙ₋₁ + n, try a particular solution An + B. Matching coefficients gives A = 2A + 1 and B = −2A + 2B, so A = −1 and B = −2. The general solution is aₙ = C·2ⁿ − n − 2, and the first term fixes C.
Two earlier terms. Rules like Fibonacci's need a characteristic quadratic rather than a single fixed point. See how Fibonacci ratios approach the golden ratio.
If the algebra keeps going wrong, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
A checklist before you write the final answer
Does the sequence start at a₀ or a₁? That decides whether the power is pⁿ or pⁿ⁻¹.
Is p = 1? Then the fixed-point formula breaks down, and the sequence is an AP.
Is the question about a limit? The sequence settles at L for every starting value only when p lies strictly between −1 and 1.
The whole method rests on the nth term of a GP. If that formula is not automatic yet, the Fermi Concept Library gives every mathematics concept its own lesson, so you can revise GPs before your next recurrence problem.
