First-order recurrence relations

First-order recurrence relations

Spec 6.1–2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A first-order recurrence relation defines un+1u_{n+1} from unu_n only, such as un+1=1.1un+30u_{n+1}=1.1u_n+30.
  • A homogeneous relation un+1=a unu_{n+1}=a\,u_n has solution un=A anu_n=A\,a^n (the complementary function).
  • For un+1−a un=bu_{n+1}-a\,u_n=b, general solution == CF ++ particular solution, with λ=b1−a\lambda=\dfrac{b}{1-a}.
  • Find AA by substituting the initial condition into the whole general solution.
  • If ∣a∣<1|a|<1 then unu_n tends to λ\lambda; if ∣a∣>1|a|>1 it diverges.

Recurrence relations as models

It defines each term from the previous one. It models repeated percentage change with a fixed amount added or removed.

A recurrence relation defines each term from the previous one, for example un+1=1.1un+30u_{n+1}=1.1u_n+30 with u1=400u_1=400.

It is first order because un+1u_{n+1} depends only on unu_n, and linear because unu_n appears only to the first power.

A percentage increase of r%r\% multiplies by 1+r1001+\frac{r}{100}; a fixed addition or removal is +b+b or −b-b.

The order of events matters: "grows by 10% and then 30 are added" gives 1.1un+301.1u_n+30, whereas adding first gives 1.1(un+30)1.1(u_n+30).

0200400600800123456nu(n)
The first six terms of u(n+1) = 1.1u(n) + 30 with u(1) = 400.

A population grows by 20% each year and then 50 are removed. Which relation models this?

Homogeneous relations

Try un=mnu_n=m^n to get the auxiliary equation m−a=0m-a=0. The solution is un=A anu_n=A\,a^n.

A first-order relation un+1=a unu_{n+1}=a\,u_n (written un+1−a un=0u_{n+1}-a\,u_n=0) is homogeneous.

Try un=mnu_n=m^n: it gives the auxiliary equation m−a=0m-a=0, so m=am=a and the solution is un=A anu_n=A\,a^n, where AA is a constant found from the initial condition.

This is also called the complementary function (CF). Its root is the common ratio aa, and the CF always has an arbitrary constant AA.

020406080100012345nu(n)
Illustrative: u(n+1) = 2u(n) with u(0) = 3 gives u(n) = 3 × 2ⁿ, a geometric sequence.
  • un+1=a unu_{n+1}=a\,u_nun=A anu_n=A\,a^n

Worked example

Solve un+1=3unu_{n+1}=3u_n with u1=2u_1=2.

Solve un+1=4unu_{n+1}=4u_n with u1=3u_1=3.

Non-homogeneous relations

The general solution is the complementary function plus a particular solution. Try a constant λ\lambda for the particular solution.

For un+1−a un=bu_{n+1}-a\,u_n=b with b≠0b\ne0, the general solution is

un=complementary function+particular solution.u_n=\text{complementary function}+\text{particular solution}.

To find a particular solution (PS) try a constant un=λu_n=\lambda. Then λ−aλ=b\lambda-a\lambda=b, so λ=b1−a\lambda=\dfrac{b}{1-a} (for a≠1a\ne1).

Add the PS to the CF before using the initial condition.

01234560123456nu(n)
  • u(n)
  • λ = 6
Illustrative: u(n+1) = 0.5u(n) + 3 with u(0) = 0. The particular solution λ = 3 ÷ (1 − 0.5) = 6 is the value the terms settle towards.
  • General solutionCF ++ PS
  • Particular solutionλ=b1−a\lambda=\dfrac{b}{1-a}

Worked example

Solve un+1−5un=8u_{n+1}-5u_n=8 with u1=1u_1=1.

Find the particular solution of un+1−2un=6u_{n+1}-2u_n=6.

Initial conditions and long-term behaviour

If ∣a∣<1|a|<1, unu_n tends to λ\lambda. If ∣a∣>1|a|>1 the complementary function grows without bound.

Substitute the starting term into the general solution to find AA, then check by computing u2u_2 directly and from your formula.

If ∣a∣<1|a|<1 then an→0a^n\to0, so unu_n tends to λ=b1−a\lambda=\frac{b}{1-a}. If ∣a∣>1|a|>1 the CF grows without bound, so unu_n diverges.

For example un+1=0.75un+200u_{n+1}=0.75u_n+200 gives λ=800\lambda=800 and the amount tends to 800.

Check the index: if the question gives u0u_0 then n=0n=0 goes into the formula, and if it gives u1u_1 then n=1n=1 does. Inequalities need logarithms; reverse the inequality when dividing by a negative logarithm.

020040060080012345678nu(n)
u(n+1) = 0.75u(n) + 200 with u(1) = 400 levels off towards 800.

What does unu_n tend to for un+1=0.5un+10u_{n+1}=0.5u_n+10?

Exam method

Rearrange, write the auxiliary equation and CF, find the PS, apply the initial condition to the whole solution, then check with u2u_2.

Follow this method in the exam.

  1. Rearrange to un+1−a un=bu_{n+1}-a\,u_n=b.
  2. Write the auxiliary equation m−a=0m-a=0 and the CF A anA\,a^n.
  3. Try un=λu_n=\lambda for the PS and solve for λ\lambda.
  4. Write the general solution, use the initial condition to find AA, and state unu_n in full.
  5. Check against u2u_2 and interpret in context.

Quote the words "complementary function", "particular solution" and "auxiliary equation": the specification expects them.

  1. 1

    Rearrange

    un+1−a un=bu_{n+1}-a\,u_n=b

  2. 2

    Auxiliary equation and CF

    m−a=0m-a=0, so CF =A an=A\,a^n

  3. 3

    Particular solution

    try un=λu_n=\lambda and solve

  4. 4

    General solution and A

    use the initial condition on the whole solution

  5. 5

    Check and interpret

    test against u2u_2 and answer in context

Exam method

What do you try for the particular solution of un+1−3un=10u_{n+1}-3u_n=10?

Try an exam question

Solve the recurrence relation un+1=2un+3u_{n+1}=2u_n+3 with u1=4u_1=4, giving unu_n in terms of nn.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find u2u_2.

1 mark, marked against the mark scheme

Revision notes