Welcome to Recurrence Relations!
Ever wondered how population growth is predicted or how your savings might grow over several years? In Decision Mathematics 2, we use Recurrence Relations to model these exact scenarios. Think of a recurrence relation as a mathematical "recipe" where each new number is cooked up using the numbers that came before it.
By the end of these notes, you'll be able to solve both first-order and second-order relations and find that "closed-form" formula that lets you jump straight to any term in the sequence!
1. The Basics: What is a Recurrence Relation?
A recurrence relation is an equation that defines a sequence of values using previous terms. We usually use the notation \( u_n \) to represent the \( n \)-th term.
Key Terms:
- Order: This tells you how far back you need to look. A first-order relation looks back one step (\( u_{n+1} \) depends on \( u_n \)). A second-order relation looks back two steps (\( u_{n+2} \) depends on \( u_{n+1} \) and \( u_n \)).
- Linear: The terms like \( u_n \) aren't squared or square-rooted.
- Homogeneous: If the equation equals zero (e.g., \( u_{n+1} - 3u_n = 0 \)).
- Non-Homogeneous: If the equation equals a constant or a function of \( n \) (e.g., \( u_{n+1} - 3u_n = 4 \)).
Analogy: Imagine you are climbing a ladder. A first-order relation is like saying "To get to the next rung, I step up from the current one." A second-order relation is like saying "To reach the next rung, I need to know the position of my last two steps to balance."
2. Solving First-Order Recurrence Relations
Let's look at the general form: \( u_{n+1} + a u_n = g(n) \).
Step A: Find the Complementary Function (CF)
The Complementary Function is the solution to the "zero version" of your equation (the homogeneous part).
For \( u_{n+1} + a u_n = 0 \), the solution is always in the form:
\( u_n = A(-a)^n \)
Step B: Find the Particular Solution (PS)
The Particular Solution deals with the "extra bit" on the end (\( g(n) \)). We "guess" a form for the PS based on what \( g(n) \) looks like:
- If \( g(n) \) is a constant (like 8), try \( u_n = \lambda \).
- If \( g(n) \) is linear (like \( 3n + 2 \)), try \( u_n = \lambda n + \mu \).
Step C: The General Solution
The General Solution is simply: \( u_n = CF + PS \).
Step D: Use Boundary Conditions
Finally, use the information given (like \( u_1 = 1 \)) to find the value of the constant \( A \).
Example from Syllabus: \( u_{n+1} - 5u_n = 8 \), with \( u_1 = 1 \).
1. CF: Solve \( u_{n+1} - 5u_n = 0 \). This gives \( u_n = A(5)^n \).
2. PS: Since 8 is a constant, let \( u_n = \lambda \). Then \( u_{n+1} = \lambda \).
Substitute: \( \lambda - 5\lambda = 8 \Rightarrow -4\lambda = 8 \Rightarrow \lambda = -2 \). So, \( PS = -2 \).
3. General Solution: \( u_n = A(5)^n - 2 \).
4. Find A: Use \( u_1 = 1 \). \( 1 = A(5)^1 - 2 \Rightarrow 3 = 5A \Rightarrow A = 0.6 \).
Final Answer: \( u_n = 0.6(5)^n - 2 \).
3. Solving Second-Order Recurrence Relations
These look like: \( a u_{n+2} + b u_{n+1} + c u_n = g(n) \).
Step 1: The Auxiliary Equation
To find the Complementary Function (CF), we create a quadratic equation using the coefficients:
\( a r^2 + b r + c = 0 \)
Depending on the roots of this quadratic (\( r_1 \) and \( r_2 \)), your CF will take a different shape:
- Two distinct real roots: \( u_n = A(r_1)^n + B(r_2)^n \)
- One repeated root: \( u_n = (A + Bn)(r_1)^n \)
Step 2: The Particular Solution (PS)
Just like first-order, look at \( g(n) \). If it's a constant, try \( u_n = \lambda \). If it's linear, try \( u_n = \lambda n + \mu \). Substitute this back into the original second-order equation to solve for the Greek letters.
Step 3: Combine and Solve
General Solution = CF + PS.
Use your two boundary conditions (usually \( u_1 \) and \( u_2 \)) to solve for \( A \) and \( B \).
Don't worry if this seems tricky at first! The process is always the same: Find the roots, pick the right formula for CF, find your PS, and then plug in your boundary values at the very end.
Quick Review:
- Auxiliary Equation: The quadratic used to find the CF roots.
- CF: The "natural" behavior of the sequence.
- PS: The "forced" behavior due to the extra function \( g(n) \).
- Boundary Conditions: Used only after combining CF and PS.
4. Modelling: Real-World Applications
Recurrence relations are perfect for Population Growth models.
Imagine a population where each year it grows by 10%, but 500 individuals emigrate.
The relation would be: \( u_{n+1} = 1.1 u_n - 500 \).
By solving this, you can predict the population for any year \( n \) without having to calculate every single year in between!
Did you know? The famous Fibonacci sequence (\( 1, 1, 2, 3, 5, 8... \)) is a second-order recurrence relation: \( u_{n+2} = u_{n+1} + u_n \). It appears everywhere in nature, from pinecones to galaxies!
5. Common Pitfalls to Avoid
- Wrong PS Choice: If your "guessed" PS is already part of your CF, you must multiply your guess by \( n \). For example, if your CF is \( A(2)^n \) and your \( g(n) \) is \( 2^n \), try \( u_n = \lambda n(2)^n \).
- Applying Boundary Conditions too early: Never find \( A \) and \( B \) using just the CF. You must add the PS first, then solve for the constants.
- Sign Errors: Be very careful with negative roots in the auxiliary equation. \( (-2)^n \) is very different from \( -2^n \)!
6. Summary: The Step-by-Step Method
To solve any recurrence relation in your exam:
- Identify the Order (1st or 2nd).
- Solve the Auxiliary Equation to find the Complementary Function (CF).
- Guess and solve for the Particular Solution (PS).
- Write the General Solution: \( u_n = CF + PS \).
- Use the given Boundary Conditions to find your constants (\( A, B \)).
Key Takeaway: Recurrence relations allow us to turn a step-by-step process into a single formula. Master the Auxiliary Equation and the PS "guesses," and you'll have the keys to solve any problem in this chapter!