First-order recurrence relations
Studying this course? Keep your progress in one place.
Key facts
- A recurrence relation defines each term from earlier ones; a closed form gives directly from .
- The solution is : complementary function plus particular solution.
- For the auxiliary equation is , so CF .
- Choose the particular solution to match , then use the starting value to find .
- 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: .
A closed form gives directly in terms of , 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 gives , not .
- First-order form
Worked example
with . Find and .
- 1
.
- 2
.
with . What is ?
Complementary function
Solve the homogeneous relation using the auxiliary equation .
Solving with constant has two parts. First solve the homogeneous relation . Try , which gives the auxiliary equation , so .
The complementary function (CF) is . For the auxiliary equation is , so the CF is .
The CF carries the arbitrary constant; it does not satisfy the full relation unless .
- 1
Homogeneous form
set the right-hand side to zero
- 2
Trial solution
substitute
- 3
Auxiliary equation
solve to get
- 4
CF
What is the complementary function of ?
The particular solution
Choose a trial form that matches , substitute and compare coefficients.
A particular solution (PS) is any single solution of the full relation. Choose its form to match :
- constant : try ;
- linear : try ;
- quadratic: try , including every term;
- : try (if is the root of the auxiliary equation, use ).
Substitute into the relation and compare coefficients.
- 1
Match g(n)
constant: λ; linear: an + b; kʳⁿ: λrⁿ
- 2
Substitute
put the trial into the full relation
- 3
Compare coefficients
equate the terms in n and the constants
- 4
Solve
find λ, or a and b
- try
- try
- try
Worked example
Find a particular solution of .
- 1
is constant, so try .
- 2
Then as well, so .
- 3
.
Worked example
Find a particular solution of .
- 1
is linear, so try .
- 2
Substituting: , which simplifies to .
- 3
Comparing coefficients of : , so .
- 4
Comparing constants: , so .
What trial form would you use for the particular solution of ?
General solution and closed form
Add the CF and PS, then use the starting value to find .
The general solution is . Use the starting value to find . If the initial term is rather than , substitute .
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
Complementary function
solve the relation with g(n) = 0
- 2
Particular solution
found by a trial form
- 3
Add them
uₙ = CF + PS
- 4
Use the start value
substitute into the whole solution to find A
- 5
Check
compare the first two terms with the recurrence
- General solutionCF + PS
Worked example
Solve with .
- 1
CF and PS , so .
- 2
When : , so .
- 3
Substitute back: .
- 4
Check: , which matches .
For with the closed form is . What is ?
Proof by induction
Use induction: check , assume , then use the recurrence to reach .
To prove a closed form is correct, use proof by induction.
- Basis: show the formula gives the right value for .
- Assumption: assume equals the formula.
- Inductive step: use the recurrence to write in terms of , substitute the assumed formula and show the result is the formula with .
- Conclusion: a full sentence, stating the result is true for all positive integers . Leaving it out loses the mark.
- 1
Basis
check n = 1
- 2
Assume
u_k equals the formula
- 3
Step
use the recurrence to reach u_(k+1)
- 4
Conclude
true for all positive integers n
Worked example
, . Prove that .
- 1
Basis: for , , which equals .
- 2
Assume .
- 3
Then .
- 4
This is the formula with .
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 , the multiplier is the growth factor and is a fixed removal each year.
The constant particular solution gives , the equilibrium value: if the population stays at 400. With the closed form is .
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 %, the multiplier is .
A population follows . What is the equilibrium value?
Try an exam question
Find the solution of the recurrence relation with , giving in terms of .
[5 marks]
- [1]Auxiliary equation , so the CF is .
- [1]Tries a constant particular solution .
- [1], so .
- [1]General solution .
- [1] gives , so and .
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
Which of the following is the complementary function of the recurrence relation?
1 mark, marked against the mark scheme