Hard Further Maths Recurrence relations Questions

Challenging, exam-style Further Maths Recurrence relations questions with worked solutions. Stretch yourself on the hardest recurrence-relations, first-order, closed-form, second-order problems.

recurrence-relationsfirst-orderclosed-formsecond-orderauxiliary-equationlucas-numbers
Further Maths34 questionsStep-by-step solutions
Question 1
9 markschallenging
Let unu_{n} be the number of ways of climbing a flight of nn stairs, taking either 11 stair or 22 stairs at each move. It can be shown that the sequence is defined by un+2=un+1+unu_{n+2}=u_{n+1}+u_{n}, n≥1n\ge 1, with u1=1u_{1}=1 and u2=2u_{2}=2. Find the number of ways of climbing a flight of 1515 stairs.
Show worked solution

Worked solution

  1. Apply the recurrence with n=1n=1

    u3=2+1=3u_{3}=2+1=3

    Each new term is built from the terms immediately before it.

  2. Apply the recurrence with n=2n=2

    u4=3+2=5u_{4}=3+2=5

    Each new term is built from the terms immediately before it.

  3. Apply the recurrence with n=3n=3

    u5=5+3=8u_{5}=5+3=8

    Each new term is built from the terms immediately before it.

  4. Apply the recurrence with n=4n=4

    u6=8+5=13u_{6}=8+5=13

    Each new term is built from the terms immediately before it.

  5. Apply the recurrence with n=5n=5

    u7=13+8=21u_{7}=13+8=21

    Each new term is built from the terms immediately before it.

  6. Apply the recurrence with n=6n=6

    u8=21+13=34u_{8}=21+13=34

    Each new term is built from the terms immediately before it.

  7. Apply the recurrence with n=7n=7

    u9=34+21=55u_{9}=34+21=55

    Each new term is built from the terms immediately before it.

  8. Apply the recurrence with n=8n=8

    u10=55+34=89u_{10}=55+34=89

    Each new term is built from the terms immediately before it.

  9. Apply the recurrence with n=9n=9

    u11=89+55=144u_{11}=89+55=144

    Each new term is built from the terms immediately before it.

  10. Apply the recurrence with n=10n=10

    u12=144+89=233u_{12}=144+89=233

    Each new term is built from the terms immediately before it.

  11. Apply the recurrence with n=11n=11

    u13=233+144=377u_{13}=233+144=377

    Each new term is built from the terms immediately before it.

  12. Apply the recurrence with n=12n=12

    u14=377+233=610u_{14}=377+233=610

    Each new term is built from the terms immediately before it.

  13. Apply the recurrence with n=13n=13

    u15=610+377=987u_{15}=610+377=987

    Each new term is built from the terms immediately before it.

  14. List the terms found so far

    u1=1,u2=2,u3=3,u4=5,u5=8u_{1}=1,\quad u_{2}=2,\quad u_{3}=3,\quad u_{4}=5,\quad u_{5}=8

    Writing the terms in a row makes a slip easy to spot.

  15. Note that no closed form is needed

    u15 follows from 13 applications of the recurrenceu_{15}\ \text{follows from 13 applications of the recurrence}

    For a small index, iterating is quicker than solving the recurrence.

  16. State the required term

    u15=987u_{15}=987

    This is the value asked for.

Answer
987987
Question 2
9 markschallenging
Let unu_{n} be the number of ways of tiling a 2×n2\times n rectangle with 2×12\times1 dominoes, where u1=1u_{1}=1 and u2=2u_{2}=2. Which of the following recurrence relations is satisfied by unu_{n}?
Show worked solution

Worked solution

  1. Count the smallest cases directly

    u1=1,u2=2,u3=3,u4=5u_{1}=1,\quad u_{2}=2,\quad u_{3}=3,\quad u_{4}=5

    Listing the tilings by hand for n=1,2,3n=1,2,3 gives the first terms.

  2. Split the tilings by what covers the left-hand end

    one vertical domino, or two stacked horizontal dominoes\text{one vertical domino, or two stacked horizontal dominoes}

    Every tiling starts in exactly one of these two ways, and the two cases do not overlap.

  3. Count each case

    vertical: un+1 ways,horizontal pair: un ways\text{vertical: }u_{n+1}\ \text{ways},\qquad\text{horizontal pair: }u_{n}\ \text{ways}

    A vertical domino leaves a 2×(n+1)2\times\left(n+1\right) rectangle; a horizontal pair leaves a 2×n2\times n rectangle.

  4. Add the two cases

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

    The addition principle gives the recurrence, which is the Fibonacci relation.

  5. Check the recurrence against the counted values

    u4=u3+u2=3+2=5u_{4}=u_{3}+u_{2}=3+2=5

    The recurrence reproduces the number of tilings that were counted by hand.

  6. Reject the option with a doubled term

    un+2=2un+1+un ⇒ u4=2×3+2≠5u_{n+2}=2u_{n+1}+u_{n}\ \Rightarrow\ u_{4}=2\times 3+2\neq 5

    It over-counts, so it cannot be the right model.

  7. Recall the auxiliary 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 the homogeneous recurrence and dividing by mnm^{n} gives this quadratic.

  8. Recall the general 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 general solution for a repeated root

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

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

  10. Recall the general 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 trigonometric form.

  11. Recall the structure of the general solution

    un=complementary function+particular solutionu_{n}=\text{complementary function}+\text{particular solution}

    The complementary function solves the homogeneous equation; the particular solution supplies f(n)f(n).

  12. Recall the standard trial particular solutions

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

    The trial solution copies the shape of f(n)f(n).

  13. Recall the resonance rule

    if the trial already solves the homogeneous equation, multiply it by n\text{if the trial already solves the homogeneous equation, multiply it by }n

    Otherwise the substitution collapses to 0=f(n)0=f(n) and no value of λ\lambda works.

  14. Recall the number of arbitrary constants

    order 1→1 constant,order 2→2 constants\text{order }1\rightarrow 1\ \text{constant},\qquad\text{order }2\rightarrow 2\ \text{constants}

    Exactly as many initial conditions are needed to pin them down.

  15. Select the recurrence

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

    The number of tilings satisfies the Fibonacci recurrence.

Answer
un+2=un+1+unu_{n+2}=u_{n+1}+u_{n}
Question 3
9 markschallenging
A sequence is defined by un+1=3un+6⋅3nu_{n+1}=3u_{n}+6\cdot 3^{n}, n≥0n\ge 0, with u0=1u_{0}=1. Which of the following is an expression for unu_{n} in terms of nn?
Show worked solution

Worked solution

  1. Solve the homogeneous recurrence

    un+1=3un ⇒ un=A3nu_{n+1}=3u_{n}\ \Rightarrow\ u_{n}=A3^{n}

    Ignoring f(n)f(n) leaves a geometric sequence.

  2. Choose a trial particular solution

    pn=λn⋅3np_{n}=\lambda n\cdot 3^{n}

    The obvious trial already solves the homogeneous equation, so it has to be multiplied by nn; without that factor the substitution would collapse to 0=f(n)0=f(n).

  3. Substitute the trial solution into the recurrence

    3n+1λ(n+1)−3⋅3nλn=6⋅3n3^{n + 1} \lambda \left(n + 1\right)-3\cdot 3^{n} \lambda n=6 \cdot 3^{n}

    Every uu in the recurrence is replaced by the trial expression.

  4. Divide through by 3n3^{n} and expand each term

    3λn+3λ−3λn=63 \lambda n + 3 \lambda- 3 \lambda n=6

    Every term carries a factor 3n3^{n}, which is never zero, so it cancels and leaves an identity in nn alone.

  5. Solve for the unknown coefficient

    λ=2\lambda=2

    This is the only choice of coefficient that makes the two sides agree for every nn.

  6. State the particular solution

    pn=2n⋅3np_{n}=2n\cdot 3^{n}

    This single sequence satisfies the full non-homogeneous recurrence.

  7. Write down the general solution

    un=A3n+2n⋅3nu_{n}=A3^{n}+2n\cdot 3^{n}

    The complementary function plus the particular solution.

  8. Use the initial condition u0=1u_{0}=1

    A=1 ⇒ A=1A = 1\ \Rightarrow\ A=1

    Substituting n=0n=0 into the general solution gives one linear equation, and a first-order recurrence has only one constant to find.

  9. Test the candidates against u1u_{1}

    u1=9u_{1}=9

    Any option that fails to reproduce this term can be discarded at once.

  10. Note the resonance

    the trial λ3n solves the homogeneous equation\text{the trial }\lambda 3^{n}\text{ solves the homogeneous equation}

    That is why the correct closed form carries a factor of nn.

  11. Recall the auxiliary 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 the homogeneous recurrence and dividing by mnm^{n} gives this quadratic.

  12. Recall the general 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.

  13. Recall the general solution for a repeated root

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

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

  14. Recall the general 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 trigonometric form.

  15. Recall the structure of the general solution

    un=complementary function+particular solutionu_{n}=\text{complementary function}+\text{particular solution}

    The complementary function solves the homogeneous equation; the particular solution supplies f(n)f(n).

  16. Recall the standard trial particular solutions

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

    The trial solution copies the shape of f(n)f(n).

  17. Select the closed form

    un=3n+2n⋅3nu_{n}=3^{n}+2n\cdot 3^{n}

    This is the only option that satisfies both the recurrence and the initial condition.

Answer
3n+2n⋅3n3^{n}+2n\cdot 3^{n}
Question 4
9 markschallenging
A sequence is defined by un+2=un+1−unu_{n+2}=u_{n+1}-u_{n}, n≥1n\ge 1, with u1=1u_{1}=1 and u2=−1u_{2}=-1. Which of the following best describes the behaviour of unu_{n} for large nn?
Show worked solution

Worked solution

  1. Find the roots that control the behaviour

    m=12−3i2,m=12+3i2m=\frac{1}{2} - \frac{\sqrt{3} i}{2},\quad m=\frac{1}{2} + \frac{\sqrt{3} i}{2}

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

  2. Find the modulus of each root

    ∣12−3i2∣=1,∣12+3i2∣=1\left|\frac{1}{2} - \frac{\sqrt{3} i}{2}\right|=1,\quad \left|\frac{1}{2} + \frac{\sqrt{3} i}{2}\right|=1

    A modulus greater than 11 means growth, less than 11 means decay and exactly 11 means neither.

  3. Generate the first few terms

    u1=1,u2=−1,u3=−2,u4=−1,u5=1,u6=2u_{1}=1,\quad u_{2}=-1,\quad u_{3}=-2,\quad u_{4}=-1,\quad u_{5}=1,\quad u_{6}=2

    The numerical behaviour must agree with what the roots predict.

  4. Note the effect of a negative or complex root

    a negative root alternates in sign; complex roots rotate\text{a negative root alternates in sign; complex roots rotate}

    Either produces an oscillation on top of the growth or the decay.

  5. Note the effect of the modulus

    ∣m∣>1⇒∣un∣→∞,∣m∣<1⇒un→0\left|m\right|>1\Rightarrow\left|u_{n}\right|\to\infty,\qquad\left|m\right|<1\Rightarrow u_{n}\to0

    The modulus is the growth factor per step.

  6. Recall the auxiliary 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 the homogeneous recurrence and dividing by mnm^{n} gives this quadratic.

  7. Recall the general 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.

  8. Recall the general solution for a repeated root

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

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

  9. Recall the general 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 trigonometric form.

  10. Recall the structure of the general solution

    un=complementary function+particular solutionu_{n}=\text{complementary function}+\text{particular solution}

    The complementary function solves the homogeneous equation; the particular solution supplies f(n)f(n).

  11. Recall the standard trial particular solutions

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

    The trial solution copies the shape of f(n)f(n).

  12. Recall the resonance rule

    if the trial already solves the homogeneous equation, multiply it by n\text{if the trial already solves the homogeneous equation, multiply it by }n

    Otherwise the substitution collapses to 0=f(n)0=f(n) and no value of λ\lambda works.

  13. Recall the number of arbitrary constants

    order 1→1 constant,order 2→2 constants\text{order }1\rightarrow 1\ \text{constant},\qquad\text{order }2\rightarrow 2\ \text{constants}

    Exactly as many initial conditions are needed to pin them down.

  14. Recall the first-order homogeneous solution

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

    A first-order homogeneous recurrence generates a geometric sequence.

  15. Recall the fixed point of a first-order recurrence

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

    A convergent sequence must converge to a fixed point of the recurrence.

  16. Select the correct description

    ∣m∣=1 ⇒ neither growth nor decay\left|m\right|=1\ \Rightarrow\ \text{neither growth nor decay}

    This is the only option consistent with the roots and with the terms generated above: The terms are periodic with period 6

Answer
The terms are periodic with period 66.
Question 5
9 markschallenging
A sequence is defined by un+1=kun+3u_{n+1}=ku_{n}+3, where kk is a constant, with u0=6u_{0}=6. Find the set of values of kk for which the sequence converges to a limit.
Show worked solution

Worked solution

  1. Write down the general solution

    un=Akn+31−k(k≠1)u_{n}=Ak^{n}+\frac{3}{1-k}\qquad\left(k\neq1\right)

    The complementary function is AknAk^{n} and the particular solution is the fixed point L=31−kL=\frac{3}{1-k}.

  2. Decide when the complementary function dies away

    Akn→0  ⟺  ∣k∣<1Ak^{n}\to0\iff\left|k\right|<1

    A geometric term tends to zero exactly when the common ratio has modulus less than 11.

  3. Deal with the excluded cases

    k=1 ⇒ un=u0+3n (diverges),k=−1 ⇒ the terms alternatek=1\ \Rightarrow\ u_{n}=u_{0}+3n\ \text{(diverges)},\qquad k=-1\ \Rightarrow\ \text{the terms alternate}

    Neither of these settles down to a limit, so both are excluded.

  4. Write the condition as an inequality

    ∣k∣<1\left|k\right|<1

    This is the modulus condition written out.

  5. Note what the limit would be

    L=31−kL=\frac{3}{1-k}

    For any kk in the range the terms converge to this fixed point.

  6. Note the behaviour outside the range

    ∣k∣>1 ⇒ ∣un∣→∞\left|k\right|>1\ \Rightarrow\ \left|u_{n}\right|\to\infty

    The geometric term then grows without limit and swamps the fixed point.

  7. Note that the initial value does not matter here

    A=6−31−k≠0 unless k=12A=6-\frac{3}{1-k}\neq0\ \text{unless}\ k=\frac{1}{2}

    Whenever ∣k∣<1\left|k\right|<1 the term AknAk^{n} dies away whatever AA is, and for ∣k∣≥1\left|k\right|\ge1 the constant AA is not zero, so the terms never settle.

  8. Recall the auxiliary 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 the homogeneous recurrence and dividing by mnm^{n} gives this quadratic.

  9. Recall the general 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.

  10. Recall the general solution for a repeated root

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

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

  11. Recall the general 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 trigonometric form.

  12. Recall the structure of the general solution

    un=complementary function+particular solutionu_{n}=\text{complementary function}+\text{particular solution}

    The complementary function solves the homogeneous equation; the particular solution supplies f(n)f(n).

  13. Recall the standard trial particular solutions

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

    The trial solution copies the shape of f(n)f(n).

  14. Recall the resonance rule

    if the trial already solves the homogeneous equation, multiply it by n\text{if the trial already solves the homogeneous equation, multiply it by }n

    Otherwise the substitution collapses to 0=f(n)0=f(n) and no value of λ\lambda works.

  15. State the set of values

    −1<k<1-1<k<1

    For exactly these values of kk the sequence converges to a limit.

Answer
−1<k<1-1<k<1

Unlock 29 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

Practice QuestionsWorked Solutions

Related Further Pure topics

Conic sections 1Conic sections 2Further complex numbersGroupsInequalitiesFurther integration techniques