Welcome to Recurrence Relations in Decision Mathematics 2
Welcome to one of the most practical and satisfying chapters in Further Mathematics (8FM0)! Have you ever wondered how banks calculate compound interest year after year, how ecologists model animal populations, or how computer algorithms solve puzzle games step-by-step? All of these processes share a common mathematical backbone: recurrence relations.
Don't worry if algebra has felt intimidating in the past. We will break down every method into manageable, step-by-step recipes. By the end of this chapter, you will be able to translate real-life scenarios into equations, solve them to find exact formulas, and prove your solutions using mathematical induction.
---1. Key Definitions and Fundamental Ideas
Before jumping into solving equations, let's establish the key terminology used throughout Decision Mathematics 2.
What is a Recurrence Relation?
A recurrence relation (sometimes called a difference equation) is a formula that defines each term of a sequence, \(u_n\) or \(x_n\), using one or more of the preceding terms (such as \(u_{n-1}\) or \(u_n\)) along with the index \(n\).
Closed-Form (Explicit) Formula:
A closed-form solution gives you the value of \(u_n\) directly in terms of \(n\) and initial constants, without needing to calculate all the terms that came before it. For example, if \(u_n = 2^n + 3\), you can jump straight to \(u_{100}\) without working out \(u_1, u_2, \dots, u_{99}\).
The Order of a Recurrence Relation:
The order is the difference between the highest and lowest subscripts of the sequence terms appearing in the relation.
• \(u_{n+1} = 3u_n + 5\) is first order because the difference between subscripts is \((n+1) - n = 1\).
• \(u_{n+2} + 4u_{n+1} - 5u_n = 0\) is second order because \((n+2) - n = 2\).
Note: For AS Level (8FM0), your solving techniques focus on first-order relations!
Linear vs. Non-Linear:
A recurrence relation is linear if every sequence term appears only to the first power and is not multiplied by any other sequence term. For example, \(u_{n+1} = 2u_n + n\) is linear, whereas \(u_{n+1} = (u_n)^2\) or \(u_{n+1} = u_n \cdot u_{n-1}\) are non-linear.
Homogeneous vs. Non-Homogeneous:
• A relation is homogeneous if every single term involves the sequence variable: \(u_{n+1} - a u_n = 0\).
• A relation is non-homogeneous if it contains a separate function of \(n\) or a standalone constant: \(u_{n+1} - a u_n = f(n)\).
Boundary / Initial Conditions:
These are specific known starting values, such as \(u_0 = 100\) or \(u_1 = 4\), which allow us to find the exact value of unknown constants in our general solution.
2. Formulating Recurrence Relations from Real-World Scenarios
In the AS exam, you are often asked to set up a recurrence relation from a written description. Let's look at three classic examples.
Scenario A: Financial Savings & Interest
Example: A saver opens an account with \(£1000\). Each year, the account earns \(5\%\) interest on the balance, and at the end of the year, the saver deposits an extra \(£200\).
• Let \(u_n\) be the amount of money in the account after \(n\) years.
• The balance in year \(n+1\) comes from the year \(n\) balance plus \(5\%\) interest, plus \(£200\):
\(u_{n+1} = 1.05 u_n + 200\), with initial condition \(u_0 = 1000\).
Scenario B: Population Models with Harvesting
Example: A fish farm starts with \(5000\) fish. The population naturally multiplies by a factor of \(1.2\) each year, but \(800\) fish are harvested at the end of each year.
• Let \(u_n\) be the fish population after \(n\) years.
• Recurrence relation: \(u_{n+1} = 1.2 u_n - 800\), with \(u_0 = 5000\).
Scenario C: The Tower of Hanoi Puzzle
Did you know? The famous Tower of Hanoi puzzle asks for the minimum number of moves, \(M_n\), required to transfer \(n\) discs from one peg to another following specific rules.
• To move \(n+1\) discs, you must first move the top \(n\) discs to a spare peg (\(M_n\) moves), move the largest bottom disc (\(1\) move), and then move the \(n\) discs on top of it again (\(M_n\) moves).
• Recurrence relation: \(M_{n+1} = 2M_n + 1\), with initial condition \(M_1 = 1\).
Key Takeaway for Formulation: Carefully identify what happens between step \(n\) and step \(n+1\), check whether the initial state starts at \(n=0\) or \(n=1\), and write down the initial value clearly.
---3. Solving First-Order Linear Recurrence Relations
To find the closed-form formula for a linear non-homogeneous relation \(u_{n+1} - a u_n = f(n)\), we use a structured three-part method:
General Solution = Complementary Function + Particular Solution
\(u_n = u_n^{(c)} + u_n^{(p)}\)
Step 1: Finding the Complementary Function (CF), \(u_n^{(c)}\)
The complementary function is the solution to the homogeneous equation where the right-hand side is set to zero:
\(u_{n+1} - a u_n = 0\)
Setting up the auxiliary equation: \(m - a = 0 \implies m = a\).
Therefore, the Complementary Function is always:
\(u_n^{(c)} = A(a)^n\)
(where \(A\) is an arbitrary constant).
Step 2: Finding the Particular Solution (PS), \(u_n^{(p)}\)
The particular solution takes care of the non-homogeneous part, \(f(n)\). We make an educated trial guess based on the form of \(f(n)\), substitute it into the recurrence relation, and solve for the unknown coefficients.
Standard Trial Forms:
• Constant: If \(f(n) = k\), try \(u_n^{(p)} = \lambda\)
Special failure case: If \(a = 1\) (i.e. \(u_{n+1} - u_n = k\)), try \(u_n^{(p)} = \lambda n\).
• Linear: If \(f(n) = pn + q\), try \(u_n^{(p)} = \lambda n + \mu\)
Special failure case: If \(a = 1\), multiply by \(n\): try \(u_n^{(p)} = n(\lambda n + \mu) = \lambda n^2 + \mu n\).
• Quadratic: If \(f(n) = pn^2 + qn + r\), try \(u_n^{(p)} = \lambda n^2 + \mu n + \nu\)
Special failure case: If \(a = 1\), multiply the entire trial form by \(n\).
• Exponential / Geometric: If \(f(n) = k(b)^n\), try \(u_n^{(p)} = \lambda (b)^n\)
Special failure case: If \(b = a\) (the base matches the CF base), try \(u_n^{(p)} = \lambda n (a)^n\).
Step 3: Finding the Arbitrary Constant \(A\)
Write out the full general solution: \(u_n = A(a)^n + u_n^{(p)}\).
Substitute the given initial condition (e.g. \(u_0\) or \(u_1\)) into the complete formula to solve for \(A\).
Worked Example: Solving a First-Order Relation
Problem: Find the closed-form solution for the recurrence relation \(u_{n+1} = 3u_n + 4n\), given that \(u_0 = 5\).
Solution:
Part 1: Complementary Function (CF)
Consider the homogeneous equation: \(u_{n+1} - 3u_n = 0\).
Auxiliary root: \(m = 3\).
So, \(u_n^{(c)} = A(3)^n\).
Part 2: Particular Solution (PS)
Here, \(f(n) = 4n\) (linear), and \(a = 3 \neq 1\).
Try \(u_n^{(p)} = \lambda n + \mu\).
Then \(u_{n+1}^{(p)} = \lambda (n + 1) + \mu = \lambda n + \lambda + \mu\).
Substitute these into \(u_{n+1} - 3u_n = 4n\):
\((\lambda n + \lambda + \mu) - 3(\lambda n + \mu) = 4n\)
\(-2\lambda n + (\lambda - 2\mu) = 4n + 0\)
Equate coefficients of \(n\) and constant terms:
• For \(n\): \(-2\lambda = 4 \implies \lambda = -2\)
• For constants: \(\lambda - 2\mu = 0 \implies -2 - 2\mu = 0 \implies \mu = -1\)
So, \(u_n^{(p)} = -2n - 1\).
Part 3: General Solution and Boundary Condition
Combine CF and PS:
\(u_n = A(3)^n - 2n - 1\)
Now apply the initial condition \(u_0 = 5\):
\(5 = A(3)^0 - 2(0) - 1\)
\(5 = A(1) - 1 \implies A = 6\)
Final Closed-Form Solution:
\(u_n = 6(3)^n - 2n - 1\)
4. Proof of Closed Forms by Mathematical Induction
Pearson Edexcel requires you to be able to prove that a given closed-form formula satisfies a recurrence relation using mathematical induction. Follow this bulletproof four-step structure to secure full marks:
Step 1: Base Case
Test the formula for the smallest given value of \(n\) (usually \(n = 0\) or \(n = 1\)). Show that the formula gives the exact value provided by the initial condition (\(\text{LHS} = \text{RHS}\)).
Step 2: Inductive Hypothesis
State clearly: "Assume the formula is true for \(n = k\), so \(u_k = g(k)\)."
Step 3: Inductive Step
Use the recurrence relation to calculate \(u_{k+1}\). Substitute your assumption for \(u_k\) and use algebra to show that the result matches \(g(k+1)\).
Step 4: Formal Conclusion
Write out the complete standard conclusion sentence. Never skip this, as examiners assign an independent mark to it!
Worked Example: Proof by Induction
Problem: A sequence is defined by \(u_{n+1} = 2u_n + 1\) with \(u_1 = 3\). Prove by mathematical induction that \(u_n = 2^{n+1} - 1\) for all integers \(n \ge 1\).
Proof:
1. Base Case: For \(n = 1\):
From the formula: \(u_1 = 2^{1+1} - 1 = 2^2 - 1 = 3\).
This matches the given initial condition \(u_1 = 3\). Therefore, the formula is true for \(n = 1\).
2. Inductive Hypothesis:
Assume the formula is true for \(n = k\), so that \(u_k = 2^{k+1} - 1\).
3. Inductive Step:
Using the recurrence relation for \(n = k + 1\):
\(u_{k+1} = 2u_k + 1\)
Substitute our inductive hypothesis for \(u_k\):
\(u_{k+1} = 2(2^{k+1} - 1) + 1\)
\(u_{k+1} = 2 \cdot 2^{k+1} - 2 + 1\)
\(u_{k+1} = 2^{(k+1)+1} - 1\)
This is the required formula with \(n = k + 1\).
4. Conclusion:
"If the statement is true for \(n = k\), it is true for \(n = k + 1\). Since it is true for \(n = 1\), it is true for all integers \(n \ge 1\) by mathematical induction."
5. Common Pitfalls and Examiner Warnings
Examiners regularly highlight avoidable mistakes in Decision Mathematics 2 papers. Keep these warnings in mind:
• Evaluating Constants Too Early: Never use \(u_0\) to find \(A\) inside the Complementary Function alone! You must write down the full general solution \(u_n = u_n^{(c)} + u_n^{(p)}\) before substituting \(n=0\) to solve for \(A\).
• Index Shift Brackets: When finding \(u_{n+1}^{(p)}\) for a linear trial \(\lambda n + \mu\), remember that \(n\) is replaced by \((n+1)\). This gives \(\lambda(n+1) + \mu = \lambda n + \lambda + \mu\). Writing \(\lambda n + \mu + 1\) is an immediate error.
• Missing the Failure Case when \(a = 1\): If you try to solve \(u_{n+1} - u_n = 5\) using a constant trial \(u_n^{(p)} = \lambda\), substituting gives \(\lambda - \lambda = 0 \neq 5\). You must recognize that when \(a=1\), you must multiply your trial by \(n\), giving \(u_n^{(p)} = \lambda n\).
• Incomplete Induction Conclusions: Omitting the conclusion or forgetting to mention both the base case and the inductive implication (\(n=k \implies n=k+1\)) will cost you the final communication mark.
• Starting Index Confusion: Always double-check whether a question specifies \(u_0\) or \(u_1\) as the initial condition.
---6. Chapter Summary & Quick Review
• Recurrence Relation: Expresses \(u_{n+1}\) in terms of previous terms like \(u_n\).
• Order: Highest subscript minus lowest subscript.
• Complementary Function (CF): Solution to \(u_{n+1} - au_n = 0\), given by \(u_n^{(c)} = A(a)^n\).
• Particular Solution (PS): Trial form matching the type of \(f(n)\), multiplied by \(n\) if it clashes with the CF.
• General Solution: \(u_n = u_n^{(c)} + u_n^{(p)} = A(a)^n + u_n^{(p)}\).
• Boundary Values: Applied at the very end to find \(A\).
• Induction: Prove Base Case \(\rightarrow\) Assume for \(n=k\) \(\rightarrow\) Show for \(n=k+1\) using the recurrence relation \(\rightarrow\) State full conclusion.