Welcome to Recurrence Relations!
In this chapter, we are going to explore Recurrence Relations (sometimes called Difference Equations). These are essentially mathematical "rulebooks" that tell you how to find the next number in a sequence based on the numbers that came before it. This is a vital part of the Extra Pure section because it allows us to model everything from bank interest to population growth and even the way digital signals are processed!
Did you know? The famous Fibonacci sequence \(1, 1, 2, 3, 5, 8, ...\) is actually a recurrence relation! Each term is the sum of the two before it: \(u_{n+2} = u_{n+1} + u_n\).
1. The Language of Recurrence Relations
Before we start solving them, we need to speak the language. A recurrence relation relates the term \(u_n\) to previous terms like \(u_{n-1}\) or \(u_{n-2}\).
Key Terms:
Order: This is how far back you have to look. If you only need the previous term (\(u_n\)), it is First Order. If you need the two previous terms (\(u_n\) and \(u_{n-1}\)), it is Second Order.
Linear: This means the terms (\(u_n, u_{n+1}, etc.\)) aren't squared, cubed, or stuck inside square roots.
Homogeneous: If the equation equals zero (e.g., \(u_{n+1} - 2u_n = 0\)), it is homogeneous. If there is a "leftover" function of \(n\) (e.g., \(u_{n+1} - 2u_n = 3n + 1\)), it is Non-Homogeneous.
Initial Conditions: These are the starting values, like \(u_0 = 5\). Without these, we can only find a "General Solution." With them, we find a "Particular Solution."
Quick Review Box: Types of Long-Run Behaviour
As \(n\) gets very large (written as \(n \to \infty\)), sequences behave differently:
1. Convergent: The terms settle down to a single number (a Limit).
2. Divergent: The terms get bigger and bigger (or smaller and smaller) forever.
3. Periodic: The terms repeat in a cycle (e.g., \(1, 0, -1, 1, 0, -1, ...\)).
4. Oscillating: The terms bounce back and forth, usually getting wider or narrower.
Key Takeaway: The order tells you how many "initial bits" of info you need to fully solve the sequence.
2. Solving First Order Relations
A first order linear relation looks like this: \(u_{n+1} = a u_n + f(n)\).
The Homogeneous Case \(u_{n+1} = a u_n\)
This is the simplest type. It's just like geometric progression! If you multiply by \(a\) every time, the general solution is simply:
\(u_n = A(a)^n\)
Example: If \(u_{n+1} = 3u_n\), then \(u_n = A(3)^n\).
The Non-Homogeneous Case \(u_{n+1} = a u_n + f(n)\)
Don't worry if this looks tricky! We solve it in two parts, just like differential equations:
Total Solution = Complementary Function (CF) + Particular Integral (PI)
Step 1: Find the CF. Ignore the \(f(n)\) and solve it as if it were zero. This gives you \(u_n = A(a)^n\).
Step 2: Find the PI. Look at \(f(n)\) and "guess" a similar form:
- If \(f(n) = \text{constant}\), guess \(u_n = \lambda\).
- If \(f(n) = \text{linear (e.g., } 2n+3\text{)}\), guess \(u_n = \lambda n + \mu\).
- If \(f(n) = \text{quadratic (e.g., } n^2\text{)}\), guess \(u_n = \lambda n^2 + \mu n + \nu\).
- If \(f(n) = d k^n\), guess \(u_n = \lambda k^n\).
Step 3: Combine and Solve. Add them together and use your initial conditions (like \(u_0\)) to find the constant \(A\).
Common Mistake: If your "guess" for the PI is already part of your CF, you must multiply your guess by \(n\). For example, if your CF is \(A(2)^n\) and \(f(n) = 2^n\), your PI guess should be \(\lambda n (2^n)\).
3. Solving Second Order Relations
These look like \(u_{n+2} + a u_{n+1} + b u_n = f(n)\). These are the "Big Boss" problems of this chapter, but the method is very logical.
Step 1: The Auxiliary Equation
To find the Complementary Function (CF), we create a quadratic equation by replacing \(u_{n+2}\) with \(m^2\), \(u_{n+1}\) with \(m\), and \(u_n\) with \(1\).
For \(u_{n+2} + a u_{n+1} + b u_n = 0\), the auxiliary equation is: \(m^2 + am + b = 0\).
Step 2: Three Types of Roots
Solve the quadratic for \(m\). The nature of the roots tells you the CF:
1. Real and Distinct Roots (\(m_1\) and \(m_2\)):
\(u_n = A(m_1)^n + B(m_2)^n\)
2. Repeated Roots (\(m_1 = m_2 = m\)):
\(u_n = (A + Bn)m^n\)
3. Complex Roots (\(m = p \pm iq\)):
First, find the modulus \(r = \sqrt{p^2 + q^2}\) and the argument \(\theta = \arctan(q/p)\).
The CF is: \(u_n = r^n (A \cos(n\theta) + B \sin(n\theta))\).
Step 3: The Particular Integral (PI)
If the equation is non-homogeneous (not equal to zero), guess a PI using the same table as the first order section. Plug your guess into the original equation to find the values of your Greek letters (\(\lambda, \mu\), etc.).
Key Takeaway: Always find the CF first! You can't find the constants \(A\) and \(B\) until you have added the CF and PI together.
4. Verification and Investigation
Sometimes the exam won't ask you to solve from scratch. Instead, it might ask you to verify a solution or investigate a limit.
Verification (Step-by-Step):
1. Take the given solution for \(u_n\).
2. Write out what \(u_{n+1}\) and \(u_{n+2}\) would look like using that formula.
3. Substitute these into the recurrence relation.
4. Simplify! If the left side equals the right side, the solution is verified.
Investigating Long-Run Behaviour:
If a sequence has a Limit \(L\), then as \(n\) gets very large, \(u_n \approx L\) and \(u_{n+1} \approx L\).
To find the limit, replace all \(u\) terms with \(L\) and solve for \(L\).
Example: For \(u_{n+1} = 0.5u_n + 3\), the limit is \(L = 0.5L + 3\), which gives \(0.5L = 3\), so \(L = 6\).
Summary Checklist
- Can you identify the order and whether it is homogeneous?
- Can you solve the Auxiliary Equation for second-order relations?
- Do you remember the modulus-argument form for complex roots?
- Do you know to multiply your PI guess by \(n\) if it overlaps with the CF?
- Can you use initial conditions to find the specific values of \(A\) and \(B\)?
Don't worry if complex roots feel strange at first! Just remember they always lead to \(\sin\) and \(\cos\) patterns, which makes sense because complex numbers on an Argand diagram represent rotation/oscillation.