First-order recurrence relations
Studying this course? Keep your progress in one place.
Key facts
- A first-order recurrence relation defines from only, such as .
- A homogeneous relation has solution (the complementary function).
- For , general solution CF particular solution, with .
- Find by substituting the initial condition into the whole general solution.
- If then tends to ; if it diverges.
Recurrence relations as models
It defines each term from the previous one. It models repeated percentage change with a fixed amount added or removed.
A recurrence relation defines each term from the previous one, for example with .
It is first order because depends only on , and linear because appears only to the first power.
A percentage increase of multiplies by ; a fixed addition or removal is or .
The order of events matters: "grows by 10% and then 30 are added" gives , whereas adding first gives .
A population grows by 20% each year and then 50 are removed. Which relation models this?
Homogeneous relations
Try to get the auxiliary equation . The solution is .
A first-order relation (written ) is homogeneous.
Try : it gives the auxiliary equation , so and the solution is , where is a constant found from the initial condition.
This is also called the complementary function (CF). Its root is the common ratio , and the CF always has an arbitrary constant .
Worked example
Solve with .
- 1
Auxiliary equation , so and .
- 2
Use : , so .
Solve with .
Non-homogeneous relations
The general solution is the complementary function plus a particular solution. Try a constant for the particular solution.
For with , the general solution is
To find a particular solution (PS) try a constant . Then , so (for ).
Add the PS to the CF before using the initial condition.
- u(n)
- λ = 6
- General solutionCF PS
- Particular solution
Worked example
Solve with .
- 1
CF: .
- 2
PS: , so .
- 3
General solution .
- 4
Use : , so .
Find the particular solution of .
Initial conditions and long-term behaviour
If , tends to . If the complementary function grows without bound.
Substitute the starting term into the general solution to find , then check by computing directly and from your formula.
If then , so tends to . If the CF grows without bound, so diverges.
For example gives and the amount tends to 800.
Check the index: if the question gives then goes into the formula, and if it gives then does. Inequalities need logarithms; reverse the inequality when dividing by a negative logarithm.
What does tend to for ?
Exam method
Rearrange, write the auxiliary equation and CF, find the PS, apply the initial condition to the whole solution, then check with .
Follow this method in the exam.
- Rearrange to .
- Write the auxiliary equation and the CF .
- Try for the PS and solve for .
- Write the general solution, use the initial condition to find , and state in full.
- Check against and interpret in context.
Quote the words "complementary function", "particular solution" and "auxiliary equation": the specification expects them.
- 1
Rearrange
- 2
Auxiliary equation and CF
, so CF
- 3
Particular solution
try and solve
- 4
General solution and A
use the initial condition on the whole solution
- 5
Check and interpret
test against and answer in context
What do you try for the particular solution of ?
Try an exam question
Solve the recurrence relation with , giving in terms of .
[4 marks]
- [1]Auxiliary equation , so the complementary function is .
- [1]Particular solution: , so .
- [1]General solution ; gives , so .
- [1] (check: ).
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find .
1 mark, marked against the mark scheme
Find .
1 mark, marked against the mark scheme