Recurrence Relations
Recurrence relations define sequences recursively, expressing each term as a function of previous ones. At MathMultiverse, we explore their role in combinatorics, algorithms, and more through clear examples and visualizations.
Types and Solutions
Definition
General form: \( a_n = f(a_{n-1}, a_{n-2}, \ldots) \).
Linear Homogeneous
\( a_n = c_1 a_{n-1} + c_2 a_{n-2} \):
\[ r^2 - c_1 r - c_2 = 0 \]
Non-Homogeneous
\( a_n = c_1 a_{n-1} + f(n) \).
Generating Functions
Fibonacci: \( G(x) = \frac{x}{1 - x - x^2} \).
First-Order
\( a_n = r a_{n-1} \):
\[ a_n = a_0 r^n \]
Examples
Fibonacci
\( a_n = a_{n-1} + a_{n-2} \), \( a_0 = 0 \), \( a_1 = 1 \):
\[ a_6 = 8 \]
Geometric
\( a_n = 4 a_{n-1} \), \( a_0 = 1 \):
\[ a_3 = 4^3 = 64 \]
Non-Homogeneous
\( a_n = 3 a_{n-1} + 2 \), \( a_0 = 1 \):
\[ a_n = 2 \cdot 3^n - 1 \]
Second-Order
\( a_n = 5 a_{n-1} - 6 a_{n-2} \), \( a_0 = 1 \), \( a_1 = 4 \):
\[ a_n = 2^n \]
Tiling
2×n board: \( a_n = a_{n-1} + a_{n-2} \).
Visualizations
Fibonacci Sequence
Applications
- Population Growth: Fibonacci model for rabbit populations.
- Algorithm Analysis: Merge sort, \( T(n) = 2 T(n/2) + n \).
- Combinatorics: Derangements, \( !n = (n-1) [!(n-1) + !(n-2)] \).
- Finance: Compound interest, \( a_n = (1 + r) a_{n-1} \).
- Physics: Fibonacci in phyllotaxis patterns.