Every SASMO paper includes at least one sequence problem that looks like a puzzle at first glance. You see numbers like 2, 5, 11, 23, 47 and you know there is a rule hiding inside. That rule is a recurrence relation. It tells you how each term connects to the ones before it. Once you learn to spot these relations, you can solve them using a handful of powerful techniques. This guide will show you exactly how to solve recurrence relations, from the simplest to the trickiest types found in SASMO.

What Exactly Is a Recurrence Relation?

A recurrence relation is a formula that connects a term in a sequence to one or more of the terms that came before it. You also need an initial condition (the first term or first few terms) to get the sequence started.

For example, the sequence 3, 7, 15, 31, 63 follows the relation:

• a(1) = 3
• a(n) = 2 * a(n-1) + 1 for n > 1

Each new term is double the previous term plus one. That is a recurrence relation. Your job in SASMO is to either find the next term or find a closed formula that lets you compute any term without listing all the previous ones.

How to Spot a Recurrence Relation in SASMO Problems

SASMO problems often hide recurrence relations inside word problems, pattern puzzles, or geometry figures. Look for these clues:

• The problem gives the first few terms of a sequence and asks for the 10th or 20th term.
• The problem describes a process that repeats, like folding paper, splitting bacteria, or stacking blocks.
• The problem says something like “each term is defined by the previous term” or “each new number depends on the one before it.”

When you see these signals, your brain should switch to recurrence mode. You can learn more about recognizing problem types in our guide on the art of pattern recognition.

The 3-Step Process to Solve Any Recurrence Relation

Follow these steps every time you face a recurrence problem in SASMO. This process works for the vast majority of competition problems.

1. Write down the relation and initial conditions. Be precise. If the problem says “each term is 3 times the previous term minus 2,” write a(n) = 3 * a(n-1) – 2 with a(1) given.

2. Classify the relation. Is it linear? Does it have constant coefficients? Is it first order (depends only on the previous term) or second order (depends on two previous terms)? Knowing the type tells you which solving method to use.

3. Apply the right solving method. For simple relations, iterate. For linear homogeneous relations, use the characteristic equation. For nonhomogeneous relations, use a combination of methods.

Let us look at each method in detail.

Method 1: Iteration (Back Substitution)

Iteration is the simplest approach. You start from the first term and apply the relation step by step until you reach the term you need. This works well when the relation is simple and the term you need is small (like the 5th or 6th term).

Example: Find the 6th term of the sequence defined by a(1) = 4 and a(n) = a(n-1) + 7.

• a(1) = 4
• a(2) = 4 + 7 = 11
• a(3) = 11 + 7 = 18
• a(4) = 18 + 7 = 25
• a(5) = 25 + 7 = 32
• a(6) = 32 + 7 = 39

The answer is 39. Iteration is straightforward, but it becomes slow if you need the 50th term. For large terms, you need a closed formula.

Method 2: Characteristic Equation for Linear Relations

When the relation is linear and has constant coefficients, you can find a closed formula using the characteristic equation. This is the most powerful method for SASMO.

For first order linear relations: a(n) = r * a(n-1)

The solution is a(n) = a(1) * r^(n-1). This is just a geometric sequence.

For second order linear relations: a(n) = p * a(n-1) + q * a(n-2)

The characteristic equation is x^2 – p*x – q = 0. Solve for x. The general solution depends on the roots.

• If the roots are distinct (r1 and r2), then a(n) = A * r1^n + B * r2^n.
• If the roots are the same (r), then a(n) = (A + B*n) * r^n.

You find A and B using the initial conditions.

Example: Solve a(n) = 5a(n-1) – 6a(n-2) with a(1) = 1 and a(2) = 2.

The characteristic equation is x^2 – 5x + 6 = 0. Factor to (x-2)(x-3) = 0. Roots are 2 and 3.

General solution: a(n) = A * 2^n + B * 3^n.

Use n=1: 2A + 3B = 1.
Use n=2: 4A + 9B = 2.

Solve the system. Multiply the first equation by 2: 4A + 6B = 2. Subtract from the second: 3B = 0, so B = 0. Then 2A = 1, so A = 0.5.

Final formula: a(n) = 0.5 * 2^n = 2^(n-1).

Check: a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 8. The relation a(n) = 5a(n-1) – 6a(n-2) gives a(3) = 52 – 61 = 4, which matches.

Method 3: Solving Nonhomogeneous Relations

Sometimes the relation has an extra term that does not depend on previous terms. For example, a(n) = 2*a(n-1) + 3. The “+3” makes it nonhomogeneous.

The standard approach is to find the homogeneous solution first (ignore the extra term), then find a particular solution, and add them together.

For SASMO problems, the extra term is usually a constant, a linear function, or an exponential. You guess the form of the particular solution and solve for the coefficients.

Example: Solve a(n) = 3*a(n-1) + 4 with a(1) = 1.

Homogeneous part: a(n) = 3*a(n-1). Solution: a_h(n) = C * 3^(n-1).

Particular solution: guess a constant K. Substitute: K = 3K + 4. Solve: -2K = 4, so K = -2.

General solution: a(n) = C * 3^(n-1) – 2.

Use a(1) = 1: C * 3^0 – 2 = 1, so C = 3.

Final: a(n) = 3 * 3^(n-1) – 2 = 3^n – 2.

Check: a(1) = 1, a(2) = 7, a(3) = 25. The relation gives a(2) = 31 + 4 = 7, a(3) = 37 + 4 = 25. Works.

Common Mistakes and How to Avoid Them

When to Use Each Method

• Use iteration when you need a small term and the relation is simple.
• Use the characteristic equation for linear relations with constant coefficients.
• Use the particular solution method for nonhomogeneous relations.
• Use substitution (guessing and checking) for nonlinear relations that appear in SASMO.

For a deeper look at how these problem types connect to other math topics, check out our article on how logical reasoning connects all SASMO math topics together.

Practice Problem Walkthrough

Let us solve a typical SASMO style problem from start to finish.

Problem: A sequence is defined by a(1) = 2, a(2) = 5, and a(n) = 4a(n-1) – 3a(n-2) for n > 2. Find a(6).

Step 1: Write down the relation and initial conditions.
– a(1) = 2, a(2) = 5
– a(n) = 4a(n-1) – 3a(n-2)

Step 2: Classify. It is a second order linear homogeneous relation with constant coefficients.

Step 3: Use the characteristic equation.
x^2 – 4x + 3 = 0
(x-1)(x-3) = 0
Roots: 1 and 3

General solution: a(n) = A * 1^n + B * 3^n = A + B * 3^n

Step 4: Use initial conditions.
n=1: A + 3B = 2
n=2: A + 9B = 5

Subtract first from second: 6B = 3, so B = 0.5
Then A = 2 – 1.5 = 0.5

Step 5: Write the closed formula.
a(n) = 0.5 + 0.5 * 3^n = 0.5 * (1 + 3^n)

Step 6: Find a(6).
a(6) = 0.5 * (1 + 729) = 0.5 * 730 = 365

The answer is 365.

Expert advice: Always check your answer by iterating the first few terms. For this problem, a(3) = 45 – 32 = 14. Your formula gives a(3) = 0.5*(1+27) = 14. The match confirms you are on the right track.

Building Your Recurrence Toolkit for SASMO

To get good at recurrence relations, you need to practice spotting the type and applying the right method. Here are the key skills to develop:

• Recognize first order vs. second order relations.
• Factor quadratic equations quickly.
• Solve systems of two linear equations.
• Test your closed formula against the first few terms.

If you want more practice with patterns, our essential practice problems for building confidence in SASMO number patterns will give you plenty of material.

Putting It All Together on Competition Day

When you see a sequence problem in SASMO, do not panic. Run through the 3-step process. Write down the relation. Classify it. Pick the method. Solve step by step. Most recurrence problems in SASMO are designed to be solved in under two minutes if you know the method.

Remember that recurrence relations also appear in other topics like combinatorics and number theory. Mastering them gives you an edge across the whole exam. For related techniques, take a look at how to use invariants to crack tough SASMO problems.

Your Next Steps

Grab a notebook and try solving five recurrence problems from past SASMO papers. Use the 3-step process for each one. Check your answers by iterating the first few terms. As you practice, the methods will become second nature. You will start spotting recurrence relations before you even finish reading the problem.

That is the moment when SASMO sequence problems stop being scary and start being fun. Go ahead and try it. You have got the tools now.