AL10, AL11 - Recurrence relationships and modelling

Recurrence relationship

A recurrence relationship defines a term using one or more earlier terms. It needs enough initial values to start the sequence. For example, $x_1=7$, $x_{n+1}=x_n+4$ for positive integers $n$, determines the sequence $7, 11, 15, \ldots$. The rule alone does not determine its starting value.

Worked example 1: adding a fixed amount

Question. Given $x_1=7$ and $x_{n+1}=x_n+4$, determine $x_4$.

Plan. Use the rule successively for $n=1, 2, 3$, recording the subscript at every step.

Why three steps? $x_1$ is already the first term. Three updates take it to the fourth term.

Answer. $x_4=19$.

Check. Starting at $7$, three additions of $4$ give $7+3(4)=19$.

Worked example 2: multiplying by a fixed amount

Question. Given $x_1=7$ and $x_{n+1}=2x_n$, determine $x_4$.

Plan. Double each new value to obtain the following term.

Why use the new value each time? The rule acts on the immediately previous term, so growth compounds rather than repeatedly doubling the original $7$.

Answer. $x_4=56$.

Check. Three doublings give $7\times2^3=56$.

Watch out

Wrong: $x_{n+1}=2x_n$ means $x_2=2(7)$, $x_3=3(7)$. The subscript does not replace the multiplier. Right: $x_3=2x_2=2(14)=28$.

Initial values

Initial values are the specified terms that start a recurrence. A rule using the previous two terms generally needs two initial values. For example, $x_1=2$ and $x_2=3$ start $x_{n+2}=x_n+x_{n+1}$; $x_1=2$ alone leaves many possible sequences.

Worked example 3: adding the previous two terms

Question. A sequence satisfies $x_1=2$, $x_2=3$ and $x_{n+2}=x_n+x_{n+1}$. Determine $x_5$.

Plan. Find $x_3$, then shift the pair of inputs forward for each new term.

Why not use $x_1$ again for $x_4$? Increasing $n$ shifts every subscript. The input pair moves from $(x_1, x_2)$ to $(x_2, x_3)$.

Answer. $x_5=13$.

Check. The terms $2, 3, 5, 8, 13$ each satisfy the stated sum rule after the first two.

Worked example 4: a weighted two-term rule

Question. Given $x_1=2$, $x_2=3$ and $x_{n+2}=2x_n+x_{n+1}$, determine $x_5$.

Plan. At each step, double the older input and add the newer one.

Why write the subscripts? The related rule $x_{n+2}=x_n+2x_{n+1}$ would give different terms: doubling the wrong input changes the sequence.

Answer. $x_5=27$.

Check. With $n=3$, the original rule gives $2x_3+x_4=14+13=27$.

Watch out

Wrong: from $x_{n+2}=2x_n+x_{n+1}$, write $x_4=2x_3+x_2$. This doubles the newer input. Right: use $n=2$ throughout, giving $x_4=2x_2+x_3$.

Exam tip

For a two-term recurrence, show the intervening terms even when only the fifth term is asked for. OCR's schemes can award separate marks for correctly determined intermediate terms, and the written indices help prevent using the wrong pair.

You already know

From GCSE, a $10\%$ increase uses multiplier $1.1$, while a $20\%$ decrease uses $0.8$. The multiplier represents the whole new amount, rather than just the amount gained or lost.

A fixed percentage update

Here $r$ is the signed percentage change per period: positive for an increase and negative for a decrease. The model assumes the same rate applies at every update.
Not on the formulae sheet: learn it.

Compound interest

Here $P$ is the initial principal, $r$ is the percentage interest rate per compounding period and $n$ is the number of completed periods. No money is paid in or taken out.
On the formulae sheet.

Worked example 5: a growing balance

Question. £5000 is invested at $4\%$ annual compound interest. Write a recurrence for the balance $B_n$, in pounds, after $n$ years and calculate $B_3$.

Plan. Start at $B_0=5000$ and multiply the current balance by $1.04$ each year.

Why not add £200 each year? Only the first year's interest is $4\%$ of £5000. Later interest is calculated on a larger balance.

Answer. $B_0=5000$, $B_{n+1}=1.04B_n$, and the balance after three years is £5624.32.

Check. The formulae-sheet expression gives $5000(1.04)^3=5624.32$.

Worked example 6: a reducing value

Question. A machine is initially worth £8000 and loses $15\%$ of its current value each year. Write a recurrence for its value $V_n$ after $n$ years and find $V_3$.

Plan. Retain $85\%$ of the current value at each update.

Why $0.85$, rather than $0.15$? $0.15V_n$ is the amount lost. $V_{n+1}$ is the amount remaining.

Answer. $V_0=8000$, $V_{n+1}=0.85V_n$, and $V_3=4913$: £4913.

Check. $8000(0.85)^3=4913$, and the values decrease while remaining positive.

Watch out

Wrong: a $12\%$ decrease gives $X_{n+1}=0.12X_n$. That keeps only $12\%$. Right: $X_{n+1}=0.88X_n$, keeping $88\%$.

Worked example 7: interest followed by a deposit

Question. A balance starts at £1000. At each year end, $10\%$ interest is added, then £100 is deposited. Let $B_n$ be the balance just after deposit number $n$, with $B_0=1000$. Form a recurrence and find $B_2$.

Plan. Multiply the previous balance by $1.1$, then add $100$.

Why is $100$ outside the multiplication? The new deposit arrives after that year's interest has been calculated, so it earns no interest in that update.

Answer. $B_0=1000$, $B_{n+1}=1.1B_n+100$, and $B_2=1420$: £1420.

Check. The second year starts with £1200, earns £120 interest and receives £100, giving £1420.

Worked example 8: a deposit followed by interest

Question. Starting from £1000, £100 is deposited at the start of each year, then $10\%$ interest is added at year end. Let $C_n$ be the balance at the end of year $n$, with $C_0=1000$. Form a recurrence and find $C_2$.

Plan. Add $100$ to the previous year-end balance, then multiply the whole amount by $1.1$.

Why the brackets? Both the old balance and the new £100 earn interest during the year.

Answer. $C_0=1000$, $C_{n+1}=1.1(C_n+100)$, and $C_2=1441$: £1441.

Check. The second year starts after the deposit with £1310; $10\%$ interest is £131, giving £1441.

Watch out

Wrong: use $1.1(B_n+100)$ for interest followed by a deposit. That pays interest on money that has not yet arrived. Right: follow the events in order, giving $1.1B_n+100$.