Introduction to Further Sequences and Series
Welcome! In this chapter of Further Pure Mathematics 2, we are going to dive into the world of recurrence relations. If you’ve ever used a formula like \( u_{n+1} = u_n + 3 \) in your earlier math studies, you’ve already met a recurrence relation!
Essentially, a recurrence relation is a rule that defines a sequence where each term depends on the ones that came before it. It’s like a set of instructions for building a staircase: to know how high the 10th step is, you need to know the height of the 9th step. In this chapter, we will learn how to turn these "step-by-step" rules into a closed form—a single formula where you can just plug in \( n \) and get the answer immediately. This is incredibly useful in computer science, population modeling, and even finance!
Don’t worry if this seems a bit abstract at first. We’ll break it down into simple stages!
1. Understanding First and Second Order Relations
Before we start solving things, we need to identify what we are looking at. Recurrence relations come in different "orders."
- First-Order Recurrence Relations: The next term depends only on the current term.
Example: \( u_{n+1} + f(n)u_n = g(n) \).
Think of this like a "yesterday" relationship. Today's value depends on yesterday's. - Second-Order Recurrence Relations: The next term depends on the two previous terms.
Example: \( u_{n+2} + f(n)u_{n+1} + g(n)u_n = h(n) \).
Think of this as a relationship with "yesterday" and "the day before yesterday." The famous Fibonacci sequence is a classic second-order relation!
Did you know? Recurrence relations are the backbone of many computer algorithms. When a program calculates something "recursively," it is literally using these mathematical rules to find the next result.
Quick Review: The order of the relation is determined by how far back in the sequence the formula looks. If it looks back two steps (from \( n+2 \) to \( n \)), it’s second-order.
2. The "Closed Form" Strategy: CF + PS
To find the closed form (a formula for \( u_n \) in terms of \( n \)), we use a two-part strategy. This is very similar to how you solve differential equations!
The General Solution is made of two parts: \[ u_n = (\text{Complementary Function}) + (\text{Particular Solution}) \]
A. The Complementary Function (CF)
The Complementary Function is the solution to the "homogeneous" version of the equation (where we set the right-hand side to zero). It represents the natural "DNA" or pattern of the sequence.
B. The Particular Solution (PS)
The Particular Solution deals with the "extra" bit on the right-hand side (the \( g(n) \) or \( h(n) \)). It’s like the specific "outfit" the sequence is wearing. We usually "guess" a form for the PS based on what the right-hand side looks like.
Common Guesses:
- If the right side is a constant (like 8), try \( u_n = \lambda \) (where \(\lambda\) is a constant).
- If the right side is linear (like \( 3n \)), try \( u_n = \lambda n + \mu \).
- If the right side is an exponential (like \( 5^n \)), try \( u_n = \lambda(5^n) \).
Key Takeaway: Always solve the CF first, then find the PS. Add them together to get your general solution!
3. Solving Second-Order Relations
When dealing with a second-order relation like \( 2u_{n+2} + 7u_{n+1} - 15u_n = 6 \), we use something called the Auxiliary Equation.
Step-by-Step Process:
- Create the Auxiliary Equation: Replace \( u_{n+2} \) with \( m^2 \), \( u_{n+1} \) with \( m \), and \( u_n \) with 1.
For example, \( 2u_{n+2} + 7u_{n+1} - 15u_n = 0 \) becomes \( 2m^2 + 7m - 15 = 0 \). - Solve for m: Factorize the quadratic to find the roots.
If the roots are \( \alpha \) and \( \beta \), then your Complementary Function is: \( u_n = A(\alpha)^n + B(\beta)^n \). - Find the Particular Solution: Since our example has a constant (6) on the right, we guess \( u_n = \lambda \), plug it into the original equation, and solve for \( \lambda \).
- Combine: Add them together! \( u_n = A(\alpha)^n + B(\beta)^n + \lambda \).
- Use Initial Conditions: Use values like \( u_1 \) and \( u_2 \) (provided in the question) to find the constants \( A \) and \( B \).
Common Mistake: Students often forget to include the PS when using initial conditions to find \( A \) and \( B \). Always combine CF and PS before plugging in your \( u_1 \) or \( u_2 \) values!
4. Proof by Induction of Closed Forms
Once you have a closed-form formula, the exam might ask you to prove it using Mathematical Induction. This is a formal way of showing that if a rule works for one step, it must work for all future steps.
The Four Steps of Induction:
- Base Case: Show the formula works for \( n=1 \).
- Assumption: Assume the formula is true for \( n=k \).
- Inductive Step: Use your assumption and the original recurrence relation to show the formula must also be true for \( n=k+1 \).
- Conclusion: Write a formal sentence stating that since it works for \( n=1 \) and \( n=k \Rightarrow n=k+1 \), it is true for all \( n \in \mathbb{Z}^+ \).
Example: If \( u_{n+1} - 3u_n = 4 \) with \( u_1 = 1 \), you might be asked to prove that \( u_n = 3^n - 2 \).
Memory Aid: Think of Induction like a row of falling dominoes. The Base Case is pushing the first domino. The Inductive Step is proving that if any domino falls, it will definitely hit the next one. If both are true, every domino in the infinite line will fall!
5. Real-World Modeling: Population Growth
Recurrence relations aren't just for exams; they model real life!
Population Growth: Imagine a population of rabbits. The number of rabbits next year (\( u_{n+1} \)) might be 1.2 times the number this year (\( u_n \)), but maybe 50 rabbits leave the forest every year.
The relation would be: \( u_{n+1} = 1.2u_n - 50 \).
By solving this, we can predict the population 100 years from now without doing 100 individual calculations!
Quick Review Box:
- Auxiliary Equation: Turns recurrence into a quadratic.
- Particular Solution: Matches the "noise" on the right side of the equals sign.
- Closed Form: A direct formula for any term \( u_n \).
Chapter Summary
Key Takeaways:
1. Recurrence relations define sequences based on previous terms.
2. To find a closed form, solve the Complementary Function using the Auxiliary Equation, find a Particular Solution, and add them together.
3. Always use initial conditions after combining the CF and PS.
4. Use Mathematical Induction to formally prove your closed-form results.
5. These models are perfect for simulating real-world scenarios like population changes or financial growth.
Great job! Recurrence relations can feel like a puzzle at first, but once you master the "CF + PS" routine, you'll be able to solve them with confidence. Keep practicing those quadratic factorizations!