Second-order recurrence relations

Second-order recurrence relations

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

Studying this course? Keep your progress in one place.

Key facts

  • A second-order recurrence relation links un+2u_{n+2}, un+1u_{n+1} and unu_n, and needs two starting values.
  • The general solution is the complementary function plus a particular solution.
  • The auxiliary equation am2+bm+c=0am^2+bm+c=0 gives the CF: two distinct roots, a repeated root, or complex roots.
  • Use both initial conditions in the whole general solution to find the two constants.
  • Induction for a second-order relation needs two base cases and two assumed terms.

What second-order means

It links three consecutive terms, so two starting values are needed.

A second-order recurrence relation links three consecutive terms: un+2+f(n)un+1+g(n)un=h(n)u_{n+2}+f(n)u_{n+1}+g(n)u_n=h(n). Two starting values, usually u1u_1 and u2u_2, define the sequence. Using only one is a common error, because there are two arbitrary constants.

When h(n)=0h(n)=0 the relation is homogeneous; otherwise it is non-homogeneous.

The method extends the first-order method: general solution == complementary function ++ particular solution.

For un+2=5un+1−6unu_{n+2}=5u_{n+1}-6u_n with u1=1u_1=1, u2=5u_2=5: u3=19u_3=19 and u4=65u_4=65.

  1. 1

    u₁ = 1 and u₂ = 5

    Two starting values are needed

  2. 2

    u₃ = 5(5) − 6(1) = 19

    Uses u₂ and u₁

  3. 3

    u₄ = 5(19) − 6(5) = 65

    Uses u₃ and u₂

For u(n+2) = 5u(n+1) − 6u(n) with u1 = 1 and u2 = 5, two starting values give every later term.
  • Second-order formun+2+f(n)un+1+g(n)un=h(n)u_{n+2}+f(n)u_{n+1}+g(n)u_n=h(n)

un+2=un+1+unu_{n+2}=u_{n+1}+u_n with u1=1u_1=1 and u2=3u_2=3. What is u4u_4?

Auxiliary equation and CF

Solve the auxiliary quadratic; the type of roots decides the form of the CF.

For aun+2+bun+1+cun=0au_{n+2}+bu_{n+1}+cu_n=0, try un=mnu_n=m^n. This gives the auxiliary equation am2+bm+c=0am^2+bm+c=0.

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

Forgetting the factor nn for a repeated root is a common error: A×3n+B×3nA\times3^n+B\times3^n has only one independent constant, so use (A+Bn)3n(A+Bn)3^n.

Distinct real roots

  • CF =A m1n+B m2n=A\,m_1^n+B\,m_2^n

Repeated root

  • CF =(A+Bn)mn=(A+Bn)m^n

Complex roots

  • rnr^n times sines and cosines of nθn\theta
  • Oscillates
−7−6−5−4−3−2−11234−20−101020304050xy(−5, 0)(1.5, 0)y = 2m² + 7m − 15
Roots of the auxiliary equation: where the curve crosses the axis.

The auxiliary equation of un+2−6un+1+9un=0u_{n+2}-6u_{n+1}+9u_n=0 is (m−3)2=0(m-3)^2=0. What is the CF?

Particular solutions

Choose a trial form to match h(n)h(n), substitute and equate coefficients.

A particular solution satisfies the full relation. Choose a trial form to match h(n)h(n): a constant λ\lambda for constant hh; an+ban+b for linear; an2+bn+can^2+bn+c for quadratic; λrn\lambda r^n for krnkr^n.

Substitute and equate coefficients. If the trial form already appears in the complementary function (for example a constant when m=1m=1 is a root), multiply it by nn.

Test your particular solution by substituting a value such as n=1n=1 into the original relation before adding the CF.

  1. 1

    Match the trial form to h(n)

    Constant, an + b or λrⁿ

  2. 2

    Substitute into the relation

    Replace uₙ, uₙ₊₁, uₙ₊₂

  3. 3

    Equate coefficients

    Solve for the unknowns

  4. 4

    Check against the CF

    If it clashes, multiply the trial by n

Finding a particular solution.
  • h(n)=kh(n)=ktry un=λu_n=\lambda
  • h(n)=pn+qh(n)=pn+qtry un=an+bu_n=an+b
  • h(n)=krnh(n)=kr^ntry un=λrnu_n=\lambda r^n

Worked example

Find a particular solution of 2un+2+7un+1−15un=62u_{n+2}+7u_{n+1}-15u_n=6.

Worked example

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

What trial form would you use for the particular solution of un+2−5un+1+6un=4×5nu_{n+2}-5u_{n+1}+6u_n=4\times5^n?

Finding the closed form

Add the CF and PS, then substitute both initial conditions into the full general solution.

Add the CF and PS, then use both initial conditions. Substitute them into the full general solution, including the particular solution.

Clear fractions before solving the simultaneous equations: multiplying by 44 gives 6A−20B=446A-20B=44 and 9A+100B=−649A+100B=-64.

A closed form gives unu_n in terms of nn alone.

  1. 1

    General solution = CF + PS

    Contains constants A and B

  2. 2

    Substitute u₁ and u₂

    Into the full solution, including the PS

  3. 3

    Solve the simultaneous equations

    Clear fractions first

  4. 4

    Closed form

    uₙ in terms of n alone

From general solution to closed form.
  • General solutionCF + PS, then use u₁ and u₂

Worked example

Solve 2un+2+7un+1−15un=62u_{n+2}+7u_{n+1}-15u_n=6 with u1=10u_1=10 and u2=−17u_2=-17.

un=A×2n+B×3nu_n=A\times2^n+B\times3^n with u1=5u_1=5 and u2=13u_2=13. What is AA?

Induction for second-order relations

Use two base cases and two assumed terms, then show the next term follows.

A second-order relation links uk+2u_{k+2} to uk+1u_{k+1} and uku_k, so the induction needs two base cases and two assumed terms.

  • Basis: check n=1n=1 and n=2n=2.
  • Assumption: assume true for n=kn=k and n=k+1n=k+1.
  • Step: write uk+2u_{k+2} using the recurrence, substitute both assumed forms and show the result is the formula with n=k+2n=k+2.
  • Conclusion: true for n=1,2n=1,2, and true for k,k+1k,k+1 implies true for k+2k+2, so true for all positive integers nn.
  1. 1

    Basis

    check n = 1 and n = 2

  2. 2

    Assume

    true for k and k + 1

  3. 3

    Step

    use the recurrence to reach k + 2

  4. 4

    Conclude

    true for all positive integers n

Second-order induction.

Worked example

un+2=3un+1−2unu_{n+2}=3u_{n+1}-2u_n, u1=1u_1=1, u2=3u_2=3. Prove that un=2n−1u_n=2^n-1.

Why does a second-order induction need two assumed terms?

Interpreting solutions

The root with the largest modulus dominates the long-term behaviour.

The closed form shows long-term behaviour. For un=3n−2nu_n=3^n-2^n the root with the largest modulus, 33, dominates, so un+1un→3\frac{u_{n+1}}{u_n}\to3.

  • A root of modulus greater than 1 makes the sequence grow.
  • A root of modulus less than 1 makes that part decay.
  • A negative root makes that part alternate in sign, like (−5)n(-5)^n.
  • A repeated root gives the extra factor nn, so growth is faster than for a single root.

Generate u3u_3 from the recurrence and from the closed form: they must agree.

0.511.522.533.544.5550100150200250xy(5, 243)(5, 32)y = 3ⁿy = 2ⁿ
3ⁿ dominates 2ⁿ as n increases (shown as continuous curves).

In un=A×0.5n+B×4nu_n=A\times0.5^n+B\times4^n, which term dominates for large nn?

Try an exam question

Solve the recurrence relation un+2−5un+1+6un=0u_{n+2}-5u_{n+1}+6u_n=0 with u1=1u_1=1 and u2=−1u_2=-1, giving unu_n in terms of nn.

[5 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which of the following gives the roots of the auxiliary equation?

1 mark, marked against the mark scheme

Revision notes