Second-order recurrence relations

Second-order recurrence relations

Spec 6.2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A second-order relation links each term to the two before: p un+2+q un+1+r un=f(n)p\,u_{n+2}+q\,u_{n+1}+r\,u_n=f(n).
  • Two initial conditions are needed because the solution has two arbitrary constants.
  • Auxiliary equation p m2+q m+r=0p\,m^2+q\,m+r=0: distinct roots give A m1n+B m2nA\,m_1^n+B\,m_2^n; a repeated root gives (A+Bn)mn(A+Bn)m^n.
  • For a constant right-hand side try un=λu_n=\lambda in every term.
  • If all ∣m∣<1|m|<1 the solution tends to the particular solution.

Second-order relations

Each term depends on the two before it. Homogeneous means the right-hand side is 0.

A second-order linear recurrence relation links each term to the two before it:

p un+2+q un+1+r un=f(n),p\,u_{n+2}+q\,u_{n+1}+r\,u_n=f(n),

where pp, qq and rr are constants.

It is homogeneous if the right-hand side is 0 and non-homogeneous if it is a non-zero constant.

Two initial conditions, such as u1u_1 and u2u_2, fix the sequence, because the solution has two arbitrary constants.

  1. 1

    Start

    u₁ and u₂ are given

  2. 2

    Next term

    u₃ from u₁ and u₂

  3. 3

    Next term

    u₄ from u₂ and u₃

  4. 4

    And so on

    always the previous two terms

Each term of a second-order recurrence is built from the two before it, so two starting values are needed.
  • Formp un+2+q un+1+r un=f(n)p\,u_{n+2}+q\,u_{n+1}+r\,u_n=f(n)

How many initial conditions fix a second-order recurrence relation?

The complementary function

Try un=mnu_n=m^n to get the auxiliary equation, then use its roots.

For the homogeneous relation try un=mnu_n=m^n. Dividing by mnm^n gives the auxiliary equation p m2+q m+r=0p\,m^2+q\,m+r=0.

The form of the complementary function depends on the roots.

For a repeated root you need (A+Bn)mn(A+Bn)m^n, not A mn+B mnA\,m^n+B\,m^n, which is only one constant.

Example: 2un+2+7un+1−15un=02u_{n+2}+7u_{n+1}-15u_n=0 gives (2m−3)(m+5)=0(2m-3)(m+5)=0, so m=32m=\frac32 or −5-5, and the CF is A(32)n+B(−5)nA\left(\frac32\right)^n+B(-5)^n.

−7−6−5−4−3−2−1123−30−20−10102030xym = 3/2m = −52m² + 7m − 15
For 2u(n+2) + 7u(n+1) − 15uₙ = 0 the auxiliary equation 2m² + 7m − 15 = 0 (x-axis is m) has roots m = 3/2 and m = −5.

Distinct real roots

Roots:
m1≠m2m_1\ne m_2
Complementary function:
A m1n+B m2nA\,m_1^n+B\,m_2^n

Repeated root

Roots:
m1=m2=mm_1=m_2=m
Complementary function:
(A+Bn) mn(A+Bn)\,m^n

Worked example

Find the complementary function of un+2−6un+1+9un=0u_{n+2}-6u_{n+1}+9u_n=0.

Find the complementary function of un+2−5un+1+6un=0u_{n+2}-5u_{n+1}+6u_n=0.

The particular solution

For a constant right-hand side try un=λu_n=\lambda in every term, then add it to the complementary function.

For a constant right-hand side, the general solution is the complementary function plus a particular solution.

Try un=λu_n=\lambda, a constant, in every term: un+2u_{n+2}, un+1u_{n+1} and unu_n all become λ\lambda. Keep the coefficients.

Example: 2un+2+7un+1−15un=62u_{n+2}+7u_{n+1}-15u_n=6 gives 2λ+7λ−15λ=62\lambda+7\lambda-15\lambda=6, so λ=−1\lambda=-1 and un=A(32)n+B(−5)n−1u_n=A\left(\frac32\right)^n+B(-5)^n-1.

  1. 1

    Complementary function

    A(3/2)ⁿ + B(−5)ⁿ

  2. 2

    Try uₙ = λ in every term

    2λ + 7λ − 15λ = 6

  3. 3

    Solve for λ

    λ = −1

  4. 4

    Add them

    uₙ = A(3/2)ⁿ + B(−5)ⁿ − 1

Finding the general solution for a constant right-hand side.
  • Particular solutiontry un=λu_n=\lambda in all three terms

Worked example

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

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

Using the initial conditions

Substitute n=1n=1 and n=2n=2 into the general solution to form two simultaneous equations.

Substitute n=1n=1 and n=2n=2 (or the values given) into the general solution to form two simultaneous equations for AA and BB.

Example: un=A(32)n+B(−5)n−1u_n=A\left(\frac32\right)^n+B(-5)^n-1 with u1=10u_1=10 and u2=−17u_2=-17 gives

32A−5B−1=10\frac32A-5B-1=10 and 94A+25B−1=−17\frac94A+25B-1=-17, so A=4A=4 and B=−1B=-1.

Check with the relation: 2u3+7(−17)−15(10)=62u_3+7(-17)-15(10)=6 gives u3=137.5u_3=137.5, and the formula gives 4×278+125−1=137.54\times\frac{27}{8}+125-1=137.5.

020406080100120140123nuₙ
The first three terms of uₙ = 4(3/2)ⁿ − (−5)ⁿ − 1, which fits u₁ = 10 and u₂ = −17 (A = 4, B = −1).
  • u1u_1 and u2u_2two equations for AA and BB

Which expression do you substitute the initial conditions into?

Long-term behaviour and exam method

A root with ∣m∣<1|m|<1 dies away. If all roots do, the solution tends to the particular solution; a root with ∣m∣>1|m|>1 makes it grow.

As n→∞n\to\infty, a term mnm^n with ∣m∣<1|m|<1 tends to 0, so the solution tends to the particular solution λ\lambda.

If any root has ∣m∣>1|m|>1 the solution grows without bound, dominated by the root of largest magnitude.

If a question asks for the first nn for which unu_n exceeds a value, test values directly when the formula has two exponential terms.

Use the words "auxiliary equation", "complementary function" and "particular solution" in your working.

  1. 1

    Auxiliary equation

    write it and solve it

  2. 2

    Complementary function

    state it from the roots

  3. 3

    Particular solution

    try un=λu_n=\lambda in every term

  4. 4

    General solution

    add the CF and the PS

  5. 5

    Initial conditions

    use both to find AA and BB

  6. 6

    Check and interpret

    test with u3u_3 and answer in context

Exam method

A second-order relation has roots 0.50.5 and −0.8-0.8 and particular solution 3. What does unu_n tend to?

Try an exam question

Find the general solution of the recurrence relation un+2−7un+1+10un=12u_{n+2}-7u_{n+1}+10u_n=12.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What are the roots of the auxiliary equation?

1 mark, marked against the mark scheme

Revision notes