26-07 — Recurrence Relations

Phase: Combinatorics | Subject: 26-07 Prerequisites: 26-03-combinations.md, 03-07-sequences-and-series.md Next subject: 26-08-generating-functions.md

Learning Objectives

By the end of this subject, you will be able to:

1. Define and classify recurrence relations (order, homogeneous vs nonhomogeneous, linear vs nonlinear)
2. Solve linear homogeneous recurrences with constant coefficients using the characteristic equation
3. Solve recurrences by iteration and back-substitution
4. Model real-world counting problems with recurrences (Fibonacci, Tower of Hanoi, Catalan)
5. Find particular solutions for nonhomogeneous recurrences

Core Content

Definitions

A recurrence relation expresses $a_n$ in terms of previous terms $a_{n-1}, a_{n-2}, \ldots$.

• Order: how far back you look. $a_n = a_{n-1} + a_{n-2}$ is order 2.
• Linear: each term appears to the first power, no products. $a_n = a_{n-1}^2$ is nonlinear.
• Homogeneous: right-hand side is zero after moving all $a$ terms left.
• Constant coefficients: coefficients of $a_{n-k}$ don't depend on $n$.
• Initial conditions: values for the first few terms, needed for a unique solution.

Solving Linear Homogeneous Recurrences (Order 2)

For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ with constant coefficients:

1. Write the characteristic equation: $r^2 = c_1 r + c_2$, or $r^2 - c_1 r - c_2 = 0$.
2. Find roots $r_1, r_2$.

Case 1: Distinct real roots. General solution: $a_n = \alpha r_1^n + \beta r_2^n$.

Case 2: Repeated root $r$. General solution: $a_n = (\alpha + \beta n) r^n$.

Case 3: Complex roots. Use polar form $r = \rho e^{\pm i\theta}$: $a_n = \rho^n (A \cos n\theta + B \sin n\theta)$.

1. Use initial conditions to solve for $\alpha, \beta$.

Fibonacci Numbers

$$F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1$$

Characteristic equation: $r^2 - r - 1 = 0$. Roots: $r = \frac{1 \pm \sqrt{5}}{2}$. General solution: $F_n = \alpha \phi^n + \beta \psi^n$ where $\phi = (1+\sqrt{5})/2$ (golden ratio), $\psi = (1-\sqrt{5})/2$.

Using initial conditions: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$ (Binet's formula).

Tower of Hanoi

Move $n$ disks from peg A to peg C (using B as auxiliary). Minimum moves $T_n$:

$$T_n = 2T_{n-1} + 1, \quad T_1 = 1$$

Solution by iteration: $T_n = 2^n - 1$.

Catalan Numbers

$$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}, \quad C_0 = 1$$

$C_n = \frac{1}{n+1}\binom{2n}{n}$ counts: balanced parentheses, binary trees, Dyck paths, triangulations of $(n+2)$-gon.

Key Terms

• Recurrence Relation
• Characteristic Equation
• Homogeneous vs Nonhomogeneous
• Binet's Formula
• Catalan Numbers

Worked Examples

Example 1: Solve $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0 = 2$, $a_1 = 5$

Solution: Characteristic: $r^2 - 5r + 6 = 0$. Roots: $r = 2, 3$. General: $a_n = \alpha \cdot 2^n + \beta \cdot 3^n$. $a_0 = \alpha + \beta = 2$, $a_1 = 2\alpha + 3\beta = 5$. Solve: $\alpha = 1, \beta = 1$. Answer: $a_n = 2^n + 3^n$.

Example 2: Tower of Hanoi

Derive $T_n = 2^n - 1$.

Solution: $T_n = 2T_{n-1} + 1 = 2(2T_{n-2}+1) + 1 = 4T_{n-2} + 3 = \cdots = 2^{n-1}T_1 + (2^{n-1} - 1)$. Since $T_1 = 1$: $T_n = 2^n - 1$.

Example 3: Repeated Roots

Solve $a_n = 4a_{n-1} - 4a_{n-2}$, $a_0 = 1$, $a_1 = 3$.

Solution: Characteristic: $r^2 - 4r + 4 = 0 \Rightarrow (r-2)^2 = 0$. Root $r=2$ (double). General: $a_n = (\alpha + \beta n)2^n$. $a_0 = \alpha = 1$. $a_1 = (1 + \beta)2 = 3 \Rightarrow \beta = 1/2$. Answer: $a_n = (1 + n/2)2^n = 2^n + n2^{n-1}$.

Quiz

Q1: What does the concept of Recurrence Relation primarily refer to in this subject?

A) The definition and application of Recurrence Relation B) A computational error related to Recurrence Relation C) A visual representation of Recurrence Relation D) A historical anecdote about Recurrence Relation

Correct: A)

• If you chose A: Recurrence Relation is defined as: the definition and application of recurrence relation. The other options describe different aspects that are not the primary focus. Correct!
• If you chose B: This is incorrect. Recurrence Relation is defined as: the definition and application of recurrence relation. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Recurrence Relation is defined as: the definition and application of recurrence relation. The other options describe different aspects that are not the primary focus.
• If you chose D: This is incorrect. Recurrence Relation is defined as: the definition and application of recurrence relation. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) The inverse operation of the formula in question B) a_{n-1}, a_{n-2}, \ldots C) An unrelated formula from a different topic D) A simplified version of a_{n-1}, a_{n-2}, \ldots...

Correct: B)

• If you chose A: This is incorrect. The formula a_{n-1}, a_{n-2}, \ldots is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: The formula a_{n-1}, a_{n-2}, \ldots is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose C: This is incorrect. The formula a_{n-1}, a_{n-2}, \ldots is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula a_{n-1}, a_{n-2}, \ldots is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Characteristic Equation?

A) It replaces all other methods in this domain B) It is primarily a historical notation system C) It is used only in advanced research contexts D) It is used to characteristic equation in mathematical analysis

Correct: D)

• If you chose A: This is incorrect. Characteristic Equation serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Characteristic Equation serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. Characteristic Equation serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: Characteristic Equation serves the purpose described in the correct answer. The other options misrepresent its role. Correct!

Q4: Which statement about Homogeneous vs Nonhomogeneous is TRUE?

A) Homogeneous vs Nonhomogeneous is mentioned only as a historical footnote B) Homogeneous vs Nonhomogeneous is not related to this subject C) Homogeneous vs Nonhomogeneous is a fundamental concept covered in this subject D) Homogeneous vs Nonhomogeneous is an advanced topic beyond this subject's scope

Correct: C)

• If you chose A: This is incorrect. Homogeneous vs Nonhomogeneous is a fundamental concept covered in this subject. This subject covers Homogeneous vs Nonhomogeneous as part of its core content.
• If you chose B: This is incorrect. Homogeneous vs Nonhomogeneous is a fundamental concept covered in this subject. This subject covers Homogeneous vs Nonhomogeneous as part of its core content.
• If you chose C: Homogeneous vs Nonhomogeneous is a fundamental concept covered in this subject. This subject covers Homogeneous vs Nonhomogeneous as part of its core content. Correct!
• If you chose D: This is incorrect. Homogeneous vs Nonhomogeneous is a fundamental concept covered in this subject. This subject covers Homogeneous vs Nonhomogeneous as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) An unrelated numerical value C) 2^n + 3^n$. D) A different result from a common mistake

Correct: C)

• If you chose A: This is incorrect. The worked examples show that the result is 2^n + 3^n$.. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is 2^n + 3^n$.. The other options represent common errors.
• If you chose C: The worked examples show that the result is 2^n + 3^n$.. The other options represent common errors. Correct!
• If you chose D: This is incorrect. The worked examples show that the result is 2^n + 3^n$.. The other options represent common errors.

Q6: How are Homogeneous vs Nonhomogeneous and Catalan Numbers related?

A) Homogeneous vs Nonhomogeneous and Catalan Numbers are closely related concepts B) Homogeneous vs Nonhomogeneous is a special case of Catalan Numbers C) Homogeneous vs Nonhomogeneous is the inverse of Catalan Numbers D) Homogeneous vs Nonhomogeneous and Catalan Numbers are completely unrelated topics

Correct: A)

• If you chose A: Both Homogeneous vs Nonhomogeneous and Catalan Numbers are covered in this subject as interconnected topics. Correct!
• If you chose B: This is incorrect. Both Homogeneous vs Nonhomogeneous and Catalan Numbers are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Homogeneous vs Nonhomogeneous and Catalan Numbers are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Homogeneous vs Nonhomogeneous and Catalan Numbers are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Definitions?

A) A common mistake is confusing Definitions with a similar concept B) Definitions is always computed the same way in all contexts C) The main error with Definitions is using it when it is not needed D) Definitions has no common misconceptions

Correct: A)

• If you chose A: Students often confuse Definitions with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose B: This is incorrect. Students often confuse Definitions with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: This is incorrect. Students often confuse Definitions with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse Definitions with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Solving Linear Homogeneous Recurrences (Order 2)?

A) Solving Linear Homogeneous Recurrences (Order 2) is not practically useful B) Avoid Solving Linear Homogeneous Recurrences (Order 2) unless explicitly instructed C) Apply Solving Linear Homogeneous Recurrences (Order 2) to solve problems in this subject's domain D) Use Solving Linear Homogeneous Recurrences (Order 2) only in pure mathematics contexts

Correct: C)

• If you chose A: This is incorrect. Solving Linear Homogeneous Recurrences (Order 2) is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. Solving Linear Homogeneous Recurrences (Order 2) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: Solving Linear Homogeneous Recurrences (Order 2) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose D: This is incorrect. Solving Linear Homogeneous Recurrences (Order 2) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. Solve $a_n = 3a_{n-1}$ with $a_0 = 5$.
   

   Click for answer

   $a_n = 5 \cdot 3^n$.

2. Solve $a_n = 7a_{n-1} - 10a_{n-2}$ with $a_0 = 2, a_1 = 1$.
   

   Click for answer

   Characteristic: $r^2 - 7r + 10 = 0$, roots $r=2,5$. $a_n = \alpha 2^n + \beta 5^n$. $a_0 = \alpha+\beta = 2$, $a_1 = 2\alpha+5\beta = 1$. Solve: $\alpha=3, \beta=-1$. $a_n = 3\cdot 2^n - 5^n$.

3. Compute $F_{10}$ using Binet's formula.
   

   Click for answer

   $\phi = 1.618034$, $\psi = -0.618034$. $F_{10} = (\phi^{10} - \psi^{10})/\sqrt{5}$. $\phi^{10} \approx 122.99187$, $\psi^{10} \approx 0.00813$. $F_{10} = (122.98374)/2.23607 = 55$ (exact).

4. Find $C_4$ (4th Catalan number).
   

   Click for answer

   $C_4 = \frac{1}{5}\binom{8}{4} = \frac{70}{5} = 14$. Sequence: 1, 1, 2, 5, 14, 42, ...

5. Solve $a_n = 2a_{n-1} - a_{n-2}$ with $a_0 = 0, a_1 = 1$.
   

   Click for answer

   Characteristic: $r^2 - 2r + 1 = 0$, repeated root $r=1$. $a_n = (\alpha + \beta n)1^n = \alpha + \beta n$. $a_0 = \alpha = 0$, $a_1 = \beta = 1$. $a_n = n$.

Summary

Key takeaways:

• Recurrences define sequences recursively; solve for explicit formulas
• Linear homogeneous with constant coefficients: use characteristic equation
• Distinct real roots: $a_n = \alpha r_1^n + \beta r_2^n$
• Repeated root $r$: $a_n = (\alpha + \beta n) r^n$
• Complex roots: $a_n = \rho^n(A \cos n\theta + B \sin n\theta)$
• Fibonacci, Tower of Hanoi, Catalan numbers are classic recurrences

Pitfalls

• Getting the sign wrong in the characteristic equation: For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, the characteristic equation is $r^2 - c_1 r - c_2 = 0$, NOT $r^2 + c_1 r + c_2 = 0$. The standard form is $a_n - c_1 a_{n-1} - c_2 a_{n-2} = 0$, and substituting $a_n = r^n$ gives $r^n - c_1 r^{n-1} - c_2 r^{n-2} = 0 \implies r^2 - c_1 r - c_2 = 0$. A sign error here propagates through the entire solution.
• Using the distinct-roots formula when roots are repeated: If the characteristic equation has a double root $r$, the general solution is $a_n = (\alpha + \beta n) r^n$, NOT $\alpha r^n + \beta r^n = (\alpha + \beta) r^n$. The latter only has one degree of freedom and cannot satisfy two initial conditions. The extra $n$ factor is essential and arises from the reduction of order technique — forgetting it is one of the most common errors in recurrence solving.
• Applying the characteristic equation method to non-homogeneous recurrences without finding a particular solution: The method solves the homogeneous part $a_n^{(h)}$, but for $a_n = c_1 a_{n-1} + c_2 a_{n-2} + f(n)$, you must also find a particular solution $a_n^{(p)}$ that satisfies the full equation. The general solution is $a_n = a_n^{(h)} + a_n^{(p)}$. Methods for finding $a_n^{(p)}$ include undetermined coefficients (when $f(n)$ is polynomial, exponential, or trigonometric) and variation of parameters.
• Forgetting to use initial conditions to determine constants: The characteristic equation gives the form of the solution (e.g., $a_n = \alpha \cdot 2^n + \beta \cdot 3^n$), but $\alpha$ and $\beta$ are determined by initial conditions. A solution without specific numeric constants is incomplete. Always plug $n=0$ and $n=1$ (or the given initial indices) into the general form and solve the resulting linear system.
• Mixing up the order of a recurrence: The order is the number of previous terms needed — $a_n = a_{n-1} + a_{n-3}$ is order 3, not order 2, because the furthest lookback is $n-3$. The characteristic equation for order $k$ is degree $k$ and requires $k$ initial conditions. If you write a degree-2 characteristic equation for an order-3 recurrence, you'll get the wrong solution.

Next Steps

Next up: 26-08-generating-functions.md — power series as a combinatorial tool for sequences and recurrences.