4.3 Recurrence relations

Many problems happen in steps. A balance changes each month; a population changes each year; the number of ways to solve a size-$n$ problem may depend on the answers for smaller sizes. A recurrence relation is an equation that describes a value using one or more earlier values. It gives us a way to model such a process or solve a problem by building its answer step by step.

Recurrences appear throughout mathematics, from sequences and counting to algorithms, probability, and growth models. This is foundational to intermediate work built on sequences and equations. OpenStax's sequence lesson is a place to practise both recurrence rules and direct formulas.

A basic idea: start, update, repeat

Suppose a collection starts with $2$ objects and gains $3$ after every round. Let $a_n$ mean its size after $n$ rounds. The starting value is $a_0=2$. The rule for the next round is

$$a_{n+1}=a_n+3\qquad(n\ge0).$$

Here $a_n$ is the current value and $a_{n+1}$ is the next one. The rule says to take the current size and add $3$. Starting from $2$, it produces $a_1=5$, $a_2=8$, and $a_3=11$. Those values form a sequence: $2,5,8,11,\ldots$.

A recurrence needs both a starting value and an update rule. The rule $a_{n+1}=a_n+3$ by itself could also produce $10,13,16,\ldots$ if it started at $a_0=10$. The starting value is called an initial condition. If the rule uses two earlier values, it may need two initial conditions. The index tells us which value is the start and when each update applies.

To set up a recurrence in a new problem, ask three questions: What quantity am I tracking? What is known at the start? How does one step change it? For a counting problem, the last question can become: how can an answer for a larger case be assembled from answers for smaller cases?

A quick tour of recurrences

The example above uses one previous value. In general, we can write

$$a_{n+1}=F(a_n),\qquad a_0\text{ given}.$$

Here $F$ stands for the operation that turns the current value into the next one. To unroll the recurrence, apply that operation repeatedly: $a_1=F(a_0)$, $a_2=F(a_1)$, and so on. Write each step in order, using the new value only after it has been calculated.

Two familiar cases are $a_{n+1}=a_n+d$, which gives $a_n=a_0+nd$, and $a_{n+1}=ra_n$, which gives $a_n=a_0r^n$. The formula for $a_n$ is an explicit rule: it finds a term directly from its index. The recurrence is a recursive rule: it finds that term from earlier terms. For the opening example, the explicit rule is $a_n=2+3n$. Both describe the same sequence, but a recurrence can be easier to write when the process itself is step by step.

The update can be more varied than adding or multiplying. For example, $a_{n+1}=ra_n+c$ combines both operations; $a_{n+1}=a_n+(n+1)$ also depends on the round number. Neither is covered by the simple arithmetic or geometric formula without further work.

For two previous terms, a rule can look like

$$w_n=w_{n-1}+w_{n-2}\quad(n\ge2),\qquad w_0,\ w_1\text{ given}.$$

Compute in increasing index order so that both inputs already exist. In applied models, check whether the update could give an impossible value, such as a negative item count, and stop or revise the model when its assumptions fail.

Application 1: a balance after interest and payment

A balance starts at $B_0=100$ units. At the end of each period, it first grows by $10\%$ and then a payment of $20$ units is made. What are the next three balances?

1. Write the order of operations. Interest multiplies the old balance by $1.1$, then payment subtracts $20$: $B_{n+1}=1.1B_n-20$.
2. Update three times. $B_1=110-20=90$; $B_2=99-20=79$; $B_3=86.9-20=66.9$.
3. Check the interpretation. The rule applies while the payment is possible. If a later update would make the balance negative, a real payment plan would instead finish at zero; the simple recurrence would no longer describe it.

Adding $10\%$ after subtracting $20$ would be a different model.

Application 2: climbing a short staircase

You may climb either one or two steps at a time. How many different step sequences reach the top of a four-step staircase?

1. Name the count. Let $w_n$ be the number of ways to reach step $n$. There is one way to stand at step $0$ (do nothing), so $w_0=1$; $w_1=1$.
2. Split by the last move. A path to step $n$ ends with a one-step move from $n-1$ or a two-step move from $n-2$. These cases are separate, so $w_n=w_{n-1}+w_{n-2}$.
3. Calculate. $w_2=2$, $w_3=3$, and $w_4=5$. The five sequences are $1111$, $112$, $121$, $211$, and $22$, where each digit is a move length.

The recurrence counts a large staircase without listing every path.