Welcome to Recurrence Relationships!
Have you ever tracked your bank balance earning regular interest with monthly deposits, or observed how a population grows year over year? If so, you have already encountered sequence rules where the next term depends on the previous terms. In CCEA AS 2 Section D (Discrete and Decision Mathematics), these are formally called recurrence relations.
Calculating values step-by-step (e.g., finding \(u_{100}\) by working out \(u_1, u_2, \dots, u_{99}\)) is tedious. Our main goal in this chapter is to discover a closed-form algebraic formula for the \(n\)th term (\(u_n\)) so we can jump directly to any term in the sequence immediately!
1. Fundamental Definitions and Terminology
Let's make sure we understand the key vocabulary used by examiners:
Recurrence Relation: An equation that expresses each term of a sequence (\(u_n\) or \(x_n\)) in terms of one or more earlier terms (such as \(u_{n-1}\) or \(u_{n-2}\)).
Order of a Recurrence Relation: The difference between the highest subscript and the lowest subscript present in the equation.
Example: In \(u_{n+1} - 3u_n = 5\), the order is \((n+1) - n = 1\) (First-Order).
Example: In \(2u_{n+2} - 5u_{n+1} + 2u_n = 0\), the order is \((n+2) - n = 2\) (Second-Order).
Linear with Constant Coefficients: Every term involving the sequence \(u_k\) is to the power of 1 (linear), and the multipliers (\(a, b, c\)) are constant numbers, not functions of \(n\).
Homogeneous vs Non-Homogeneous:
• Homogeneous: No "extra" function of \(n\) standing alone: \(a u_{n+1} + b u_n = 0\) or \(a u_{n+2} + b u_{n+1} + c u_n = 0\).
• Non-Homogeneous: There is a non-zero right-hand side \(f(n)\): \(a u_{n+1} + b u_n = f(n)\) or \(a u_{n+2} + b u_{n+1} + c u_n = f(n)\).
General Solution vs Particular / Unique Solution:
• General Solution: An algebraic formula containing arbitrary constants (like \(A\) and \(B\)) that represents all possible sequences satisfying the recurrence relation.
• Particular / Unique Solution: The single exact formula obtained once the arbitrary constants are calculated using given initial / boundary conditions (e.g., \(u_0 = 4\), \(u_1 = 7\)).
Key Takeaway: Before solving, always identify the order (first or second) and whether the equation is homogeneous (\(f(n) = 0\)) or non-homogeneous (\(f(n) \neq 0\)).
2. The Master Structure: General Solution
For any linear recurrence relation with a right-hand side \(f(n)\), the complete General Solution is formed by combining two parts:
\(u_n = u_n^{(c)} + u_n^{(p)}\)
• \(u_n^{(c)}\) (Complementary Function): The solution to the corresponding homogeneous relation (setting the right-hand side equal to 0). This part always contains the arbitrary constants \(A\) (and \(B\) for second-order).
• \(u_n^{(p)}\) (Particular Integral): A specific sequence that satisfies the non-zero right-hand side \(f(n)\). It contains no arbitrary constants.
Analogy: Think of the Complementary Function as the core engine of a car (it defines how the sequence naturally evolves), while the Particular Integral is the external cruise control pushing it along with extra fuel \(f(n)\).
3. First-Order Linear Recurrence Relations
The standard first-order form is: \(a u_{n+1} + b u_n = f(n)\)
A. Homogeneous Case: \(a u_{n+1} + b u_n = 0\)
Rearranging gives: \(u_{n+1} = \left(-\frac{b}{a}\right) u_n\)
This is a standard geometric progression with common ratio \(\lambda = -\frac{b}{a}\).
General Solution: \(u_n = A \lambda^n\), where \(A\) is an arbitrary constant determined by \(u_0\) (so \(u_n = u_0 \lambda^n\)).
B. Non-Homogeneous Case: \(a u_{n+1} + b u_n = f(n)\)
1. Find the Complementary Function: \(u_n^{(c)} = A \lambda^n\) where \(\lambda = -\frac{b}{a}\).
2. Find the Particular Integral (\(u_n^{(p)}\)) by trying a trial form matching \(f(n)\):
• If \(f(n) = k\) (a constant): Try \(u_n^{(p)} = C\).
Special Case: If \(\lambda = 1\), try \(u_n^{(p)} = C n\).
• If \(f(n) = pn + q\) (a linear polynomial): Try \(u_n^{(p)} = P n + Q\).
• If \(f(n) = k \cdot r^n\) (geometric form): Try \(u_n^{(p)} = C \cdot r^n\).
Special Case: If \(r = \lambda\), try \(u_n^{(p)} = C n r^n\).
Worked Example (First-Order):
Problem: Solve \(u_{n+1} - 3u_n = 4\) given that \(u_0 = 5\).
Step 1: Complementary Function (\(u_n^{(c)}\))
Set the homogeneous part: \(u_{n+1} - 3u_n = 0 \implies \lambda - 3 = 0 \implies \lambda = 3\).
So, \(u_n^{(c)} = A(3^n)\).
Step 2: Particular Integral (\(u_n^{(p)}\))
Since the right-hand side is a constant (\(4\)), try \(u_n^{(p)} = C\).
Substitute \(u_{n+1} = C\) and \(u_n = C\) into the original equation:
\(C - 3C = 4 \implies -2C = 4 \implies C = -2\).
So, \(u_n^{(p)} = -2\).
Step 3: Form the Full General Solution
\(u_n = u_n^{(c)} + u_n^{(p)} = A(3^n) - 2\)
Step 4: Use Initial Conditions to find \(A\)
Substitute \(n = 0\) and \(u_0 = 5\):
\(5 = A(3^0) - 2 \implies 5 = A(1) - 2 \implies A = 7\).
Final Unique Solution: \(u_n = 7(3^n) - 2\).
4. Second-Order Linear Recurrence Relations
The standard second-order form is: \(a u_{n+2} + b u_{n+1} + c u_n = f(n)\)
A. The Auxiliary Equation (Characteristic Equation)
To find the Complementary Function \(u_n^{(c)}\), set the right-hand side to 0 and try \(u_n = \lambda^n\):
\(a \lambda^2 + b \lambda + c = 0\)
Solving this quadratic equation yields three distinct cases:
Case 1: Two Distinct Real Roots (\(\lambda_1 \neq \lambda_2\))
\(u_n^{(c)} = A \lambda_1^n + B \lambda_2^n\)
Case 2: Repeated Real Root (\(\lambda_1 = \lambda_2 = \lambda\))
\(u_n^{(c)} = (A + B n) \lambda^n\)
Case 3: Complex Conjugate Roots (\(\lambda = p \pm i q = r e^{\pm i\theta} = r (\cos \theta \pm i \sin \theta)\))
Here, the modulus is \(r = \sqrt{p^2 + q^2}\) and argument \(\theta = \arctan\left(\frac{q}{p}\right)\).
\(u_n^{(c)} = r^n (A \cos(n\theta) + B \sin(n\theta))\)
B. Trial Forms for the Particular Integral (\(u_n^{(p)}\))
Match the structure of \(f(n)\):
• If \(f(n) = k\) (constant): Try \(u_n^{(p)} = C\).
• If \(f(n) = pn + q\) (linear polynomial): Try \(u_n^{(p)} = P n + Q\).
• If \(f(n) = k \cdot \mu^n\) (exponential): Try \(u_n^{(p)} = C \cdot \mu^n\).
The Modification Rule: If any part of your trial \(u_n^{(p)}\) is already present in your Complementary Function \(u_n^{(c)}\), you must multiply your trial form by \(n\) (or by \(n^2\) if it matches a repeated root) to avoid duplication.
Worked Example (Second-Order):
Problem: Find the general solution of \(u_{n+2} - 5u_{n+1} + 6u_n = 2n + 1\).
Step 1: Complementary Function
Auxiliary equation: \(\lambda^2 - 5\lambda + 6 = 0\)
Factorise: \((\lambda - 2)(\lambda - 3) = 0 \implies \lambda_1 = 2, \; \lambda_2 = 3\).
So, \(u_n^{(c)} = A(2^n) + B(3^n)\).
Step 2: Particular Integral
Since \(f(n) = 2n + 1\) is linear, try \(u_n^{(p)} = P n + Q\).
Then \(u_{n+1} = P(n+1) + Q = Pn + P + Q\)
And \(u_{n+2} = P(n+2) + Q = Pn + 2P + Q\).
Substitute these into the recurrence relation:
\((Pn + 2P + Q) - 5(Pn + P + Q) + 6(Pn + Q) = 2n + 1\)
Expand and collect like terms:
\((P - 5P + 6P)n + (2P + Q - 5P - 5Q + 6Q) = 2n + 1\)
\(2Pn + (-3P + 2Q) = 2n + 1\)
Equate coefficients of \(n\) and constant terms:
• For \(n\): \(2P = 2 \implies P = 1\)
• Constant term: \(-3(1) + 2Q = 1 \implies 2Q = 4 \implies Q = 2\)
So, \(u_n^{(p)} = n + 2\).
Step 3: General Solution
\(u_n = u_n^{(c)} + u_n^{(p)} = A(2^n) + B(3^n) + n + 2\).
5. Step-by-Step Problem Solving Strategy
Follow this 5-step checklist for every exam question:
1. Classify: Check the order (1st or 2nd) and determine if it is homogeneous or non-homogeneous.
2. Find \(u_n^{(c)}\): Write the auxiliary equation, solve for \(\lambda\), and write down the complementary function with constants \(A\) (and \(B\)).
3. Find \(u_n^{(p)}\): If \(f(n) \neq 0\), pick an appropriate trial form, substitute into the recurrence relation, and solve for the unknown coefficients.
4. Assemble General Solution: Write out \(u_n = u_n^{(c)} + u_n^{(p)}\).
5. Apply Boundary Conditions LAST: Substitute initial values (such as \(u_0, u_1\)) into the full general solution to find the values of \(A\) and \(B\).
6. Common Pitfalls and Examiner Advice
Don't lose marks to common mistakes identified in CCEA examiner reports:
• The Number One Error — Premature Substitution: Never try to find the arbitrary constants \(A\) and \(B\) using only the complementary function \(u_n^{(c)}\). You must add \(u_n^{(p)}\) to get the complete \(u_n\) before substituting initial conditions like \(u_0\) and \(u_1\).
• Algebraic Expansion Errors: When substituting \(u_n = Pn + Q\) into \(u_{n+1}\), write \(P(n+1) + Q = Pn + P + Q\). A common mistake is writing \(Pn + 1 + Q\), which will give incorrect coefficients.
• Index Starting Points: Pay close attention to whether the given boundary conditions start at \(n = 0\) (e.g., \(u_0, u_1\)) or at \(n = 1\) (e.g., \(u_1, u_2\)).
• Exam Working Conventions: In Unit AS 2 (SFM21), working must be clearly shown in black ink. Marks are awarded for Method (M), Working/Accuracy (W), and combined Method & Working (MW). Round non-exact final numerical answers to three significant figures unless told otherwise.
Quick Review Summary
• First-order: \(u_n^{(c)} = A \lambda^n\)
• Second-order distinct roots: \(u_n^{(c)} = A \lambda_1^n + B \lambda_2^n\)
• Second-order repeated root: \(u_n^{(c)} = (A + Bn)\lambda^n\)
• Second-order complex roots: \(u_n^{(c)} = r^n(A\cos(n\theta) + B\sin(n\theta))\)
• Full solution: \(u_n = u_n^{(c)} + u_n^{(p)}\)
• Initial conditions are substituted into the full general solution at the very end!