Second-order recurrence relations
Studying this course? Keep your progress in one place.
Key facts
- A second-order recurrence relation links , and , and needs two starting values.
- The general solution is the complementary function plus a particular solution.
- The auxiliary equation 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: . Two starting values, usually and , define the sequence. Using only one is a common error, because there are two arbitrary constants.
When the relation is homogeneous; otherwise it is non-homogeneous.
The method extends the first-order method: general solution complementary function particular solution.
For with , : and .
- 1
u₁ = 1 and u₂ = 5
Two starting values are needed
- 2
u₃ = 5(5) − 6(1) = 19
Uses u₂ and u₁
- 3
u₄ = 5(19) − 6(5) = 65
Uses u₃ and u₂
- Second-order form
with and . What is ?
Auxiliary equation and CF
Solve the auxiliary quadratic; the type of roots decides the form of the CF.
For , try . This gives the auxiliary equation .
For example gives , so or and the complementary function is .
Forgetting the factor for a repeated root is a common error: has only one independent constant, so use .
Distinct real roots
- CF
Repeated root
- CF
Complex roots
- times sines and cosines of
- Oscillates
The auxiliary equation of is . What is the CF?
Particular solutions
Choose a trial form to match , substitute and equate coefficients.
A particular solution satisfies the full relation. Choose a trial form to match : a constant for constant ; for linear; for quadratic; for .
Substitute and equate coefficients. If the trial form already appears in the complementary function (for example a constant when is a root), multiply it by .
Test your particular solution by substituting a value such as into the original relation before adding the CF.
- 1
Match the trial form to h(n)
Constant, an + b or λrⁿ
- 2
Substitute into the relation
Replace uₙ, uₙ₊₁, uₙ₊₂
- 3
Equate coefficients
Solve for the unknowns
- 4
Check against the CF
If it clashes, multiply the trial by n
- try
- try
- try
Worked example
Find a particular solution of .
- 1
is constant, so try .
- 2
Then , so .
Worked example
Find a particular solution of .
- 1
is linear, so try .
- 2
Substituting: .
- 3
Equate to : , so , and , so .
What trial form would you use for the particular solution of ?
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 gives and .
A closed form gives in terms of alone.
- 1
General solution = CF + PS
Contains constants A and B
- 2
Substitute u₁ and u₂
Into the full solution, including the PS
- 3
Solve the simultaneous equations
Clear fractions first
- 4
Closed form
uₙ in terms of n alone
- General solutionCF + PS, then use u₁ and u₂
Worked example
Solve with and .
- 1
CF: . PS: . So .
- 2
From : .
- 3
From : .
- 4
Solving gives and .
- 5
Check: and .
with and . What is ?
Induction for second-order relations
Use two base cases and two assumed terms, then show the next term follows.
A second-order relation links to and , so the induction needs two base cases and two assumed terms.
- Basis: check and .
- Assumption: assume true for and .
- Step: write using the recurrence, substitute both assumed forms and show the result is the formula with .
- Conclusion: true for , and true for implies true for , so true for all positive integers .
- 1
Basis
check n = 1 and n = 2
- 2
Assume
true for k and k + 1
- 3
Step
use the recurrence to reach k + 2
- 4
Conclude
true for all positive integers n
Worked example
, , . Prove that .
- 1
Basis: and , which match and .
- 2
Assume and .
- 3
Then .
- 4
, the formula with .
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 the root with the largest modulus, , dominates, so .
- 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 .
- A repeated root gives the extra factor , so growth is faster than for a single root.
Generate from the recurrence and from the closed form: they must agree.
In , which term dominates for large ?
Try an exam question
Solve the recurrence relation with and , giving in terms of .
[5 marks]
- [1]Auxiliary equation .
- [1]Roots and .
- [1]General solution .
- [1] and .
- [1], , so .
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
Which of the following gives the roots of the auxiliary equation?
1 mark, marked against the mark scheme