Recurrence Relations

A term-to-term rule in symbols

A term-to-term rule says how to get from each term to the next. For 3, 7, 11, 15, … the rule is "add 4". A recurrence relation writes that rule in symbols.

Name the terms u₁, u₂, u₃, and so on. The small number is a subscript, and it gives the position of the term: u₁ is the first term and u₂ is the second. The rule "add 4" says u₂ = u₁ + 4, then u₃ = u₂ + 4, then u₄ = u₃ + 4. In general, each term is the term before it plus 4, which is written uₙ₊₁ = uₙ + 4.

The rule acts on each term to make the next: 3 + 4 = 7, 7 + 4 = 11 and 11 + 4 = 15.

A rule needs a start

The rule uₙ₊₁ = uₙ + 4 on its own does not say what the first term is. Starting from u₁ = 3 it gives 3, 7, 11, 15, …, but starting from u₁ = 5 it gives 5, 9, 13, 17, …, which is a different sequence with the same rule. So a recurrence relation always comes with its first term: uₙ₊₁ = uₙ + 4, with u₁ = 3.

The same rule from u₁ = 5 gives 5, 9, 13, 17, a different sequence.

Two terms back

A recurrence can use more than one earlier term. The Fibonacci sequence, from Sequences Worth Knowing, starts with u₁ = 1 and u₂ = 1, and each term after that is the sum of the two terms before it: uₙ₊₂ = uₙ₊₁ + uₙ. So u₃ = 1 + 1 = 2, u₄ = 2 + 1 = 3, u₅ = 3 + 2 = 5 and u₆ = 5 + 3 = 8.

A rule that looks two terms back needs two starting terms, u₁ and u₂, before it can make anything.

Each new block of dots is the term two places back: u₅ is u₄ = 3 with a block of u₃ = 2 dots added, which makes 5.

Running a rule

To use a recurrence relation, apply the rule one step at a time. Take u₁ = 2 and the rule uₙ₊₁ = 2uₙ − 1: double the term, then subtract 1. Then u₂ = 2 × 2 − 1 = 3, u₃ = 2 × 3 − 1 = 5 and u₄ = 2 × 5 − 1 = 9.

Each term needs the one before it, so to find u₄ you must find u₂ and u₃ first. The rule acts on the previous term, not on the position: u₄ is 2 × u₃ − 1 = 2 × 5 − 1 = 9, not 2 × 4 − 1 = 7.

Double, then subtract 1, three times over: 2 becomes 3, then 5, then 9.

A number that does not change

Recurrence relations describe things that change year by year. In the next problem, the number of trout in a lake grows and then some are caught. The count starts at year 0, so the first term is u₀ rather than u₁.

One number is special: the number the rule leaves unchanged. If L goes in and L comes out, then L = 1.2L − 300, an equation to solve. The last step multiplies a sum by 1.2, which multiplies each part of it: 1.2 × (1500 + e) = 1.2 × 1500 + 1.2 × e = 1800 + 1.2e.

Worked example: Trout in a Lake with a Yearly Catch, and the Number of Trout That Stays the Same

Question At the start of 2026 a lake holds 2000 trout. Each year the number of trout grows by 20%, and then 300 trout are caught. (a) Write a recurrence relation for u_n, the number of trout n years after the start of 2026, and find u₃. (b) Find the number of trout that would stay the same from year to year with this catch. A second lake starts with 1400 trout and has the same growth and the same catch. How many trout does it hold after 2 years, and what happens to it after that?

1.Growing by 20% multiplies the number of trout by 1.2, and the catch then takes 300 away. So u_n+1 = 1.2u_n − 300, with u₀ = 2000.

Growth multiplies by 1.2, then the catch takes 300: u_n+1 = 1.2u_n − 300.
2.Apply the rule one year at a time: u₁ = 1.2 × 2000 − 300 = 2100 and u₂ = 1.2 × 2100 − 300 = 2220.

One year at a time: u₁ = 2100 and u₂ = 2220.
3.(a) u₃ = 1.2 × 2220 − 300 = 2664 − 300 = 2364 trout.

(a) u₃ = 1.2 × 2220 − 300 = 2364 trout.
4.A number L that stays the same satisfies L = 1.2L − 300. Subtract L from both sides: 0.2L = 300, so L = 1500. Check: 1.2 × 1500 − 300 = 1500.

A steady number satisfies L = 1.2L − 300, so L = 1500.
5.Write the number of trout as 1500 + e_n, where e_n is the gap from 1500. Then 1500 + e_n+1 = 1.2(1500 + e_n) − 300 = 1500 + 1.2e_n, so e_n+1 = 1.2e_n: the gap grows by 20% each year, whether it is above 1500 or below.

With u_n = 1500 + e_n, the gap obeys e_n+1 = 1.2e_n.
6.(b) 1500 trout would stay the same. The second lake starts 100 below that: 1.2 × 1400 − 300 = 1380 after one year and 1.2 × 1380 − 300 = 1356 after two. Its gap below 1500 keeps growing, so it holds fewer trout every year and cannot keep up a catch of 300. Above 1500 the model has the trout growing without limit; a real lake runs short of food long before that, so the model is only used for the next few years.

(b) 1500 stays the same; the 1400 lake falls to 1380, then 1356, then about 1327.

Answer: (a) u_n+1 = 1.2u_n − 300 with u₀ = 2000, and u₃ = 2364 trout; (b) 1500 trout; the second lake holds 1356 trout after 2 years and keeps falling

Common mistakes

Taking the catch away before the growth, u_n+1 = 1.2(u_n − 300). The question says the trout grow first and are caught after, so 300 is subtracted after multiplying by 1.2.
Expecting every lake to move toward the steady value of 1500. Here the gap from 1500 is multiplied by 1.2 each year, so a lake that starts near 1500 moves away from it.

More sequences and series problems, worked step by step →