Further Maths Recurrence relations Practice Questions

Free Further Maths Recurrence relations practice questions with full step-by-step worked solutions. Covers recurrence-relations, first-order, modelling, tower-of-hanoi. Practise exam-style problems and check your method.

recurrence-relationsfirst-ordermodellingtower-of-hanoipopulationdepreciation
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
In the Tower of Hanoi puzzle, unu_{n} is the least number of single-disc moves needed to transfer a tower of nn discs. The model is un+1=2un+1u_{n+1}=2u_{n}+1 for n≥1n\ge 1, with u1=1u_{1}=1. Find the least number of moves needed for a tower of 66 discs, that is the value of u6u_{6}.
Show worked solution

Worked solution

  1. Apply the model with n=1n=1

    u2=2⋅1+(1)=3u_{2}=2\cdot 1+\left(1\right)=3

    Each new value comes straight from the model applied to the value just before it.

  2. Apply the model with n=2n=2

    u3=2⋅3+(1)=7u_{3}=2\cdot 3+\left(1\right)=7

    Each new value comes straight from the model applied to the value just before it.

  3. State the required value

    u6=63u_{6}=63

    This is the quantity the model is asked for.

Answer
6363
Question 2
2 markseasy
A leaking reservoir loses a fixed fraction of its excess each day; unu_{n} is the depth, in metres, after nn days. The model is un+1=12unu_{n+1}=\frac{1}{2}u_{n} for n≥0n\ge 0, with u0=8u_{0}=8. Which of the following best describes the long-term behaviour of unu_{n}?
Show worked solution

Worked solution

  1. Find the roots that control the model

    m=12m=\frac{1}{2}

    The long-run behaviour is decided entirely by the roots.

  2. Find the modulus of each root

    ∣12∣=12\left|\frac{1}{2}\right|=\frac{1}{2}

    A modulus above 11 means growth, below 11 decay, and exactly 11 neither.

  3. Generate the first few values

    u0=8, u1=4, u2=2, u3=1, u4=12, u5=14u_{0}=8,\ u_{1}=4,\ u_{2}=2,\ u_{3}=1,\ u_{4}=\frac{1}{2},\ u_{5}=\frac{1}{4}

    The numerical behaviour must agree with what the roots predict.

  4. Select the correct description

    behaviour consistent with the roots and the values above\text{behaviour consistent with the roots and the values above}

    This is the only option matching both the roots and the generated values.

Answer
The terms converge to 00.
Question 3
4 marksintermediate
A forced discrete oscillator gives a sequence unu_{n}. Here unu_{n} satisfies un+1=3un+7u_{n+1}=3u_{n}+7. Which of the following is the correct form for a particular solution?
Show worked solution

Worked solution

  1. Identify the forcing term f(n)f(n)

    f(n)=7f(n)=7

    The particular solution must copy the shape of f(n)f(n).

  2. Solve the homogeneous part first

    roots m=3\text{roots }m=3

    The homogeneous solution decides whether the obvious trial is usable.

  3. Confirm there is no resonance

    the shape of f(n) is not a homogeneous solution\text{the shape of }f(n)\text{ is not a homogeneous solution}

    No extra factor of nn is needed.

  4. Recall the rule for a repeated shape

    multiply the trial by n once for each clash with the CF\text{multiply the trial by }n\text{ once for each clash with the CF}

    This mirrors the repeated-root rule for the auxiliary equation.

  5. Note what would otherwise go wrong

    0=f(n)0=f(n)

    A trial that solves the homogeneous part contributes nothing on the left.

  6. Recall how a recurrence generates a sequence

    un+1 (or un+2) is built from the earlier term(s)u_{n+1}\ \text{(or }u_{n+2}\text{) is built from the earlier term(s)}

    A recurrence relation says how to get the next term from the ones before it, so the whole sequence follows from the starting value(s).

  7. Select the correct trial form

    pn=λp_{n}=\lambda

    This is the trial that yields a genuine particular solution.

Answer
λ\lambda
Question 4
6 markshard
A Tower of Hanoi variant needs un=2un−1+1u_{n}=2u_{n-1}+1 moves; equivalently unu_{n} satisfies un+1=2un+1u_{n+1}=2u_{n}+1 with u0=0u_{0}=0. The model is un+1=2un+1u_{n+1}=2u_{n}+1 for n≥0n\ge 0, with u0=0u_{0}=0. Find the least number of moves for 1010 discs, that is the value of u10u_{10}.
Show worked solution

Worked solution

  1. Apply the model with n=0n=0

    u1=2⋅0+(1)=1u_{1}=2\cdot 0+\left(1\right)=1

    Each new value comes straight from the model applied to the value just before it.

  2. Apply the model with n=1n=1

    u2=2⋅1+(1)=3u_{2}=2\cdot 1+\left(1\right)=3

    Each new value comes straight from the model applied to the value just before it.

  3. Apply the model with n=2n=2

    u3=2⋅3+(1)=7u_{3}=2\cdot 3+\left(1\right)=7

    Each new value comes straight from the model applied to the value just before it.

  4. Apply the model with n=3n=3

    u4=2⋅7+(1)=15u_{4}=2\cdot 7+\left(1\right)=15

    Each new value comes straight from the model applied to the value just before it.

  5. Apply the model with n=4n=4

    u5=2⋅15+(1)=31u_{5}=2\cdot 15+\left(1\right)=31

    Each new value comes straight from the model applied to the value just before it.

  6. Apply the model with n=5n=5

    u6=2⋅31+(1)=63u_{6}=2\cdot 31+\left(1\right)=63

    Each new value comes straight from the model applied to the value just before it.

  7. List the values found so far

    u0=0, u1=1, u2=3, u3=7, u4=15u_{0}=0,\ u_{1}=1,\ u_{2}=3,\ u_{3}=7,\ u_{4}=15

    Writing the run of values in order makes an arithmetic slip easy to spot.

  8. Note the model itself

    un+1=2un+1u_{n+1}=2u_{n}+1

    Every step is one substitution into this relation.

  9. Recall how a recurrence generates a sequence

    un+1 (or un+2) is built from the earlier term(s)u_{n+1}\ \text{(or }u_{n+2}\text{) is built from the earlier term(s)}

    A recurrence relation says how to get the next term from the ones before it, so the whole sequence follows from the starting value(s).

  10. State the required value

    u10=1023u_{10}=1023

    This is the quantity the model is asked for.

Answer
10231023
Question 5
9 markschallenging
A drug-infusion model each hour keeps 30%30\% of the current dose and a steady 1414 milligrams is infused; unu_{n} is the amount, in milligrams, after nn hours. The model is un+1=310un+14u_{n+1}=\frac{3}{10}u_{n}+14 for n≥0n\ge 0, with u0=5u_{0}=5. Find the long-run amount LL that unu_{n} approaches.
Show worked solution

Worked solution

  1. Set both terms equal to the steady value LL

    L=3L10+14L = \frac{3 L}{10} + 14

    If the model settles then consecutive terms tend to the same value, so the limit is a fixed point of the recurrence.

  2. Solve for the steady state

    7L10=14 ⇒ L=20\frac{7 L}{10}=14\ \Rightarrow\ L=20

    Collecting the LL terms gives one linear equation.

  3. Justify that the model really settles

    ∣310∣<1\left|\frac{3}{10}\right|<1

    The transient part A(310)nA\left(\frac{3}{10}\right)^{n} decays because the growth factor has modulus below 11.

  4. Step through a few values as a check

    u0=5, u1=312, u2=37320, u3=3919200u_{0}=5,\ u_{1}=\frac{31}{2},\ u_{2}=\frac{373}{20},\ u_{3}=\frac{3919}{200}

    The values are visibly closing in on the fixed point.

  5. Note the closed-form structure

    un=A(310)n+20u_{n}=A\left(\frac{3}{10}\right)^{n}+20

    The geometric part dies away and only the fixed point survives.

  6. Recall how a recurrence generates a sequence

    un+1 (or un+2) is built from the earlier term(s)u_{n+1}\ \text{(or }u_{n+2}\text{) is built from the earlier term(s)}

    A recurrence relation says how to get the next term from the ones before it, so the whole sequence follows from the starting value(s).

  7. Recall the auxiliary (characteristic) equation

    un+2=aun+1+bun ⇒ m2−am−b=0u_{n+2}=au_{n+1}+bu_{n}\ \Rightarrow\ m^{2}-am-b=0

    Trying un=mnu_{n}=m^{n} in a homogeneous second-order recurrence and dividing by mnm^{n} gives this quadratic.

  8. Recall the solution for two distinct real roots

    un=Aαn+Bβnu_{n}=A\alpha^{n}+B\beta^{n}

    Each root of the auxiliary equation contributes one geometric term.

  9. Recall the solution for a repeated root

    un=(A+Bn)αnu_{n}=\left(A+Bn\right)\alpha^{n}

    A repeated root supplies one solution, so the second carries a factor nn.

  10. Recall the solution for complex roots

    un=rn(Acos⁡nθ+Bsin⁡nθ)u_{n}=r^{n}\left(A\cos n\theta+B\sin n\theta\right)

    Writing the conjugate roots as r(cos⁡θ±isin⁡θ)r\left(\cos\theta\pm i\sin\theta\right) turns the solution into a real oscillation.

  11. Recall the fixed point of a first-order model

    L=aL+b ⇒ L=b1−a(a≠1)L=aL+b\ \Rightarrow\ L=\frac{b}{1-a}\quad\left(a\neq1\right)

    A model that settles down must settle to a fixed point of its recurrence.

  12. Recall the condition for a model to settle

    ∣a∣<1 for the geometric part to die away\left|a\right|<1\ \text{for the geometric part to die away}

    A growth factor of modulus 11 or more makes the transient persist or explode.

  13. Recall the first-order homogeneous solution

    un+1=aun ⇒ un=Aanu_{n+1}=au_{n}\ \Rightarrow\ u_{n}=Aa^{n}

    A constant multiplier each step produces a geometric sequence.

  14. Recall how many starting values are needed

    order 1→1 value,order 2→2 values\text{order }1\rightarrow 1\ \text{value},\qquad\text{order }2\rightarrow 2\ \text{values}

    Exactly that many initial conditions are needed to pin the model down.

  15. Recall the standard trial particular solutions

    f(n)=c⇒λ; f(n)=cn+d⇒λn+μ; f(n)=ckn⇒λknf(n)=c\Rightarrow\lambda;\ f(n)=cn+d\Rightarrow\lambda n+\mu;\ f(n)=ck^{n}\Rightarrow\lambda k^{n}

    The particular solution copies the shape of the forcing term f(n)f(n).

  16. State the long-run value

    L=20L=20

    This is the value the model approaches as nn grows.

Answer
2020

Unlock 65 more Recurrence relations questions

Create a free account to work through every Further Maths Recurrence relations question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Recurrence relations practice

Hard QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks