First-order recurrence relations

First-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 recurrence relation defines each term from earlier ones; a closed form gives unu_n directly from nn.
  • The solution is un=CF+PSu_n=\text{CF}+\text{PS}: complementary function plus particular solution.
  • For un+1+fun=g(n)u_{n+1}+fu_n=g(n) the auxiliary equation is m+f=0m+f=0, so CF =A(−f)n=A(-f)^n.
  • Choose the particular solution to match g(n)g(n), then use the starting value to find AA.
  • Prove a closed form by induction; an equilibrium value is the constant particular solution.

What a recurrence relation is

Each term is defined from the previous one; a closed form gives any term directly.

A recurrence relation defines each term of a sequence from earlier terms. A first-order relation involves only consecutive terms: un+1+f(n)un=g(n)u_{n+1}+f(n)u_n=g(n).

A closed form gives unu_n directly in terms of nn, so you can find any term without working through all the earlier ones.

With a starting value you can generate terms one at a time. Rearranging un+1−5un=8u_{n+1}-5u_n=8 gives un+1=5un+8u_{n+1}=5u_n+8, not 5un−85u_n-8.

051015202530u₁u₂u₃u₄u₅termvalue
Terms generated by uₙ₊₁ = 2uₙ + 1 with u₁ = 1
  • First-order formun+1+f(n)un=g(n)u_{n+1}+f(n)u_n=g(n)

Worked example

un+1−5un=8u_{n+1}-5u_n=8 with u1=1u_1=1. Find u2u_2 and u3u_3.

un+1=2un−3u_{n+1}=2u_n-3 with u1=4u_1=4. What is u3u_3?

Complementary function

Solve the homogeneous relation using the auxiliary equation m+f=0m+f=0.

Solving un+1+fun=g(n)u_{n+1}+fu_n=g(n) with constant ff has two parts. First solve the homogeneous relation un+1+fun=0u_{n+1}+fu_n=0. Try un=Amnu_n=Am^n, which gives the auxiliary equation m+f=0m+f=0, so m=−fm=-f.

The complementary function (CF) is un=A(−f)nu_n=A(-f)^n. For un+1−5un=8u_{n+1}-5u_n=8 the auxiliary equation is m−5=0m-5=0, so the CF is A×5nA\times5^n.

The CF carries the arbitrary constant; it does not satisfy the full relation unless g(n)=0g(n)=0.

  1. 1

    Homogeneous form

    set the right-hand side to zero

  2. 2

    Trial solution

    substitute un=mnu_n=m^n

  3. 3

    Auxiliary equation

    solve m−5=0m-5=0 to get m=5m=5

  4. 4

    CF

    un=A×5nu_n=A\times5^n

Finding the complementary function.

What is the complementary function of un+1+3un=10u_{n+1}+3u_n=10?

The particular solution

Choose a trial form that matches g(n)g(n), substitute and compare coefficients.

A particular solution (PS) is any single solution of the full relation. Choose its form to match g(n)g(n):

  • constant kk: try λ\lambda;
  • linear pn+qpn+q: try an+ban+b;
  • quadratic: try an2+bn+can^2+bn+c, including every term;
  • krnkr^n: try λrn\lambda r^n (if rr is the root of the auxiliary equation, use λnrn\lambda nr^n).

Substitute into the relation and compare coefficients.

  1. 1

    Match g(n)

    constant: λ; linear: an + b; kʳⁿ: λrⁿ

  2. 2

    Substitute

    put the trial into the full relation

  3. 3

    Compare coefficients

    equate the terms in n and the constants

  4. 4

    Solve

    find λ, or a and b

Finding a particular solution
  • g(n)=kg(n)=ktry un=λu_n=\lambda
  • g(n)=pn+qg(n)=pn+qtry un=an+bu_n=an+b
  • g(n)=krng(n)=kr^ntry un=λrnu_n=\lambda r^n

Worked example

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

Worked example

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

What trial form would you use for the particular solution of un+1−2un=3n2u_{n+1}-2u_n=3n^2?

General solution and closed form

Add the CF and PS, then use the starting value to find AA.

The general solution is un=CF+PSu_n=\text{CF}+\text{PS}. Use the starting value to find AA. If the initial term is u0u_0 rather than u1u_1, substitute n=0n=0.

Substitute the initial condition into the whole general solution, after adding the particular solution, not into the CF alone.

Always check against the first two terms generated directly from the recurrence.

  1. 1

    Complementary function

    solve the relation with g(n) = 0

  2. 2

    Particular solution

    found by a trial form

  3. 3

    Add them

    uₙ = CF + PS

  4. 4

    Use the start value

    substitute into the whole solution to find A

  5. 5

    Check

    compare the first two terms with the recurrence

From the relation to a closed form
  • General solutionCF + PS

Worked example

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

For un+1−5un=8u_{n+1}-5u_n=8 with u1=1u_1=1 the closed form is un=3×5n−1−2u_n=3\times5^{n-1}-2. What is u4u_4?

Proof by induction

Use induction: check n=1n=1, assume uku_k, then use the recurrence to reach uk+1u_{k+1}.

To prove a closed form is correct, use proof by induction.

  • Basis: show the formula gives the right value for n=1n=1.
  • Assumption: assume uku_k equals the formula.
  • Inductive step: use the recurrence to write uk+1u_{k+1} in terms of uku_k, substitute the assumed formula and show the result is the formula with n=k+1n=k+1.
  • Conclusion: a full sentence, stating the result is true for all positive integers nn. Leaving it out loses the mark.
  1. 1

    Basis

    check n = 1

  2. 2

    Assume

    u_k equals the formula

  3. 3

    Step

    use the recurrence to reach u_(k+1)

  4. 4

    Conclude

    true for all positive integers n

Induction for a closed form.

Worked example

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

Which of these is the first line of the inductive step?

Modelling with recurrences

The constant particular solution is the equilibrium value the model settles towards or moves away from.

In a model such as Pn+1=1.15Pn−60P_{n+1}=1.15P_n-60, the multiplier 1.151.15 is the growth factor and −60-60 is a fixed removal each year.

The constant particular solution λ=1.15λ−60\lambda=1.15\lambda-60 gives λ=400\lambda=400, the equilibrium value: if Pn=400P_n=400 the population stays at 400. With P1=500P_1=500 the closed form is Pn=100(1.15)n−1+400P_n=100(1.15)^{n-1}+400.

Because the multiplier is greater than 1, the population grows without limit above 400. Comment on limitations: real populations do not grow at a constant rate. For a percentage increase of rr%, the multiplier is 1+r1001+\frac{r}{100}.

0100200300400500600123456Year nPopulation
Population from P1 = 500, rounded to 1 d.p.

A population follows Pn+1=1.15Pn−60P_{n+1}=1.15P_n-60. What is the equilibrium value?

Try an exam question

Find the solution of the recurrence relation un+1−2un=3u_{n+1}-2u_n=3 with u1=4u_1=4, 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 is the complementary function of the recurrence relation?

1 mark, marked against the mark scheme

Revision notes