8.2 Linear Recurrence Relations: Characteristic Roots & Particular Solutions

Back to Discrete Mathematics Notes

📚Module 08: Combinatorics & Recurrence RelationsTopic 8.2: Linear Recurrence Relations & Characteristic Roots⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Compounding Bank Interest & The Fibonacci Rabbit Pair

Think of recurrence relations as dynamic feedback loops over discrete time steps:

1. The Recursive Definition: You deposit $1,000 in a bank account that pays 5% annual compound interest. Your balance at year $n$ depends on your balance at year $n - 1$: $$a_n = 1.05 \cdot a_{n-1}$$ To find your balance at year 50 without calculating all 50 intermediate years step-by-step, you need a closed-form formula: $a_n = 1000 \cdot (1.05)^n$.
2. The Characteristic Root Magic: For linear homogeneous equations like $a_n = 5a_{n-1} - 6a_{n-2}$, we hypothesize that the solution grows exponentially like an interest rate ($a_n = r^n$). Substituting $r^n$ collapses the recurrence into a simple algebraic polynomial ($r^2 - 5r + 6 = 0$). Factoring this polynomial unlocks the exact growth trajectory of the discrete system!
3. Homogeneous vs Non-Homogeneous:
   • Homogeneous ($F(n) = 0$): The system runs purely on internal momentum ($a_n = c_1 a_{n-1} + c_2 a_{n-2}$).
   • Non-Homogeneous ($F(n) \neq 0$): External energy or inputs are applied at every step ($+ F(n)$, such as depositing an extra $100 every year). The total solution is the sum of internal momentum ($a_n^{(h)}$) plus the steady-state response to the external drive ($a_n^{(p)}$).

💻 Bridging to Computer Science: Dynamic Programming, Divide-and-Conquer & State Invariants

In computer science:

• Algorithm Complexity Analysis: Analyzing recursive algorithms (Merge Sort, Binary Search, Tower of Hanoi) produces recurrences solved via characteristic roots, iteration trees, or the Master Theorem.
• Dynamic Programming (DP): Finding the $n$-th Fibonacci number in $O(\log n)$ time using fast matrix exponentiation: $$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$$
• Combinatorial Bit-String Constraints: Counting valid binary strings with no consecutive 1s or strings avoiding forbidden sub-patterns naturally models as a 2nd-order linear recurrence.
• Queueing Theory & Markov Chains: Steady-state probability distributions across server request queues satisfy linear recurrence systems.

📑Table of Contents

• 📐 Linear Homogeneous Recurrence Relations (LHRR-CC)
• ⚡ The Characteristic Equation & Root Multiplicity Cases
• 🚀 Linear Non-Homogeneous Recurrence Relations
• 📝 Step-by-Step Worked Examples
  • Example 1: Solving the Classic Fibonacci Recurrence (Binet's Formula)
  • Example 2: Solving a Non-Homogeneous Recurrence with Resonance
  • Example 3: Binary Strings with No Consecutive 1s
• 🎯 Exam & Interview Pitfall Check

---

📐 Linear Homogeneous Recurrence Relations (LHRR-CC)

📖Definition 8.1: Linear Homogeneous Recurrence Relationdefinition

A Linear Homogeneous Recurrence Relation of Degree $k$ with Constant Coefficients (LHRR-CC) has the standard form:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + c_3 a_{n-3} + \dots + c_k a_{n-k}$$

where:

1. $c_1, c_2, \dots, c_k$ are real numbers with $c_k \neq 0$.
2. The relation is linear because each term $a_{n-i}$ appears strictly to the first power (no non-linear terms like $a_{n-1}^2$ or $a_{n-1} a_{n-2}$).
3. The relation is homogeneous because there is no isolated function of $n$ (no independent $+ F(n)$ term).
4. The degree (or order) is $k$ (the difference between the highest index $n$ and the lowest index $n - k$).

Initial Conditions: A recurrence of degree $k$ strictly requires $k$ initial values ($a_0, a_1, \dots, a_{k-1}$) to uniquely determine the sequence.

---

⚡ The Characteristic Equation & Root Multiplicity Cases

To solve $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$, we test the exponential ansatz:

$$a_n = r^n \quad (r \neq 0)$$

Substituting $a_{n-i} = r^{n-i}$ yields:

$$r^n = c_1 r^{n-1} + c_2 r^{n-2} + \dots + c_k r^{n-k}$$

Dividing across by $r^{n-k}$ produces the Characteristic Equation:

$$r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0$$

✓ Analytical Solution Workflow

Mechanical flow: Factor characteristic polynomial for aₙ⁽ʰ⁾, determine trial particular solution aₙ⁽ᵖ⁾, and apply initial values.

Architecture Flow

The 3 Characteristic Root Solution Regimes

Formulating the general homogeneous solution based on the algebraic roots of the characteristic polynomial

🌱Case 1

Distinct Real Roots

k distinct real roots r₁, r₂, ..., rₖ. General solution: aₙ = α₁ r₁ⁿ + α₂ r₂ⁿ + ... + αₖ rₖⁿ.

→

If Roots Repeat

🔄Case 2

Repeated Real Roots

Root r has multiplicity m. General solution introduces polynomial factors: (α₀ + α₁ n + ... + αₘ₋₁ nᵐ⁻¹) rⁿ.

→

If Roots are Complex

🌀Case 3

Complex Conjugate Roots

Roots r = ρ e^(±iθ). Express via Euler's identity: ρⁿ (α₁ cos(nθ) + α₂ sin(nθ)).

📐Theorem 8.4: Master Solution for Repeated Characteristic Rootstheorem

Let the characteristic equation have $t$ distinct roots $r_1, r_2, \dots, r_t$ with multiplicities $m_1, m_2, \dots, m_t$ respectively (such that $\sum_{i=1}^t m_i = k$). The general solution to the homogeneous recurrence relation is:

$$a_n = \sum_{i=1}^{t} \left( \alpha_{i, 0} + \alpha_{i, 1} n + \alpha_{i, 2} n^2 + \dots + \alpha_{i, m_i - 1} n^{m_i - 1} \right) r_i^n$$

where the $k$ unknown constants $\alpha_{i, j}$ are uniquely solved by substituting the $k$ initial boundary conditions.

---

🚀 Linear Non-Homogeneous Recurrence Relations

When an external driving term $F(n)$ is present:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} + F(n)$$

📐Theorem 8.5: Decomposition of Non-Homogeneous Solutiontheorem

The total general solution $a_n$ is the linear superposition of two independent components:

$$a_n = a_n^{(h)} + a_n^{(p)}$$

1. $a_n^{(h)}$ (Homogeneous Solution): The general solution to the associated homogeneous recurrence ($F(n) = 0$). Contains $k$ arbitrary constants $\alpha_i$.
2. $a_n^{(p)}$ (Particular Solution): A specific sequence satisfying the non-homogeneous equation with no arbitrary constants.

The Method of Undetermined Coefficients

Standard trial templates for the particular solution aₙ⁽ᵖ⁾

📈

Exponential: F(n) = c · sⁿ

Geometric Drive

• If s is NOT a characteristic root: Trial aₙ⁽ᵖ⁾ = A · sⁿ.
• If s IS a root with multiplicity m: Trial aₙ⁽ᵖ⁾ = A · nᵐ · sⁿ.
• Crucial: The factor nᵐ breaks linear dependence (resonance).

🔢

Polynomial: F(n) = Pₜ(n)

Degree t Drive

• If 1 is NOT a characteristic root: Trial aₙ⁽ᵖ⁾ = Aₜ nᵗ + ... + A₁ n + A₀.
• If 1 IS a root with multiplicity m: Trial aₙ⁽ᵖ⁾ = nᵐ (Aₜ nᵗ + ... + A₀).
• Example: For F(n) = n, trial is A₁n + A₀ (or n(A₁n + A₀) if r=1 is root).

⚙️

Compound: F(n) = Pₜ(n) · sⁿ

General Form

• Combines both polynomial and geometric driving terms.
• Trial form: aₙ⁽ᵖ⁾ = nᵐ (Aₜ nᵗ + ... + A₁ n + A₀) · sⁿ.
• Substitute into full recurrence and equate coefficients.

🔒

Crucial Rule of Initial Conditions

Order of Operations

• NEVER evaluate constants αᵢ on aₙ⁽ʰ⁾ alone!
• Always combine aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ FIRST.
• Fit initial conditions (a₀, a₁, ...) exclusively to the full sum.

---

📝 Step-by-Step Worked Examples

Example 1: Solving the Classic Fibonacci Recurrence (Binet's Formula)

Problem Statement: Solve the Fibonacci recurrence relation:

$$F_n = F_{n-1} + F_{n-2} \quad \text{for } n \ge 2$$

with initial conditions $F_0 = 0$ and $F_1 = 1$.

Step-by-Step Solution:

1. Step 1: Form the Characteristic Equation

   • The recurrence is $F_n - F_{n-1} - F_{n-2} = 0$.
   • Substitute $F_n = r^n$: $$r^2 - r - 1 = 0$$

2. Step 2: Solve for Characteristic Roots

   • Applying the quadratic formula: $$r = \frac{-(-1) \pm \sqrt{(-1)^2 - 4(1)(-1)}}{2(1)} = \frac{1 \pm \sqrt{5}}{2}$$
   • The two distinct roots are: $$r_1 = \frac{1 + \sqrt{5}}{2} \quad (\text{The Golden Ratio } \phi), \qquad r_2 = \frac{1 - \sqrt{5}}{2} \quad (\hat{\phi})$$

3. Step 3: Write the General Solution

   • By Case 1 (distinct real roots): $$F_n = \alpha_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + \alpha_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n$$

4. Step 4: Solve for Constants using Initial Conditions

   • For $n = 0$: $$F_0 = \alpha_1 + \alpha_2 = 0 \implies \alpha_2 = -\alpha_1$$
   • For $n = 1$: $$F_1 = \alpha_1 \left(\frac{1 + \sqrt{5}}{2}\right) - \alpha_1 \left(\frac{1 - \sqrt{5}}{2}\right) = 1$$ $$\alpha_1 \left( \frac{1 + \sqrt{5} - 1 + \sqrt{5}}{2} \right) = \alpha_1 \sqrt{5} = 1 \implies \alpha_1 = \frac{1}{\sqrt{5}}$$ $$\alpha_2 = -\frac{1}{\sqrt{5}}$$

5. Step 5: Final Closed-Form (Binet's Formula)

   $$F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right]$$

Key Takeaway: Even though the closed-form formula involves the irrational number $\sqrt{5}$, all square roots cancel out identically for every integer $n \ge 0$, always yielding an integer output!

---

Example 2: Solving a Non-Homogeneous Recurrence with Resonance

Problem Statement: Solve the non-homogeneous recurrence relation:

$$a_n - 4a_{n-1} + 4a_{n-2} = 2^n \quad \text{for } n \ge 2$$

with initial conditions $a_0 = 1$ and $a_1 = 2$.

Step-by-Step Solution:

1. Step 1: Solve the Associated Homogeneous Recurrence

   • Characteristic equation: $r^2 - 4r + 4 = 0 \implies (r - 2)^2 = 0$.
   • Root $r = 2$ has multiplicity $m = 2$.
   • Homogeneous solution: $$a_n^{(h)} = (\alpha_0 + \alpha_1 n) \cdot 2^n$$

2. Step 2: Determine Particular Solution $a_n^{(p)}$ (Resonance Detection)

   • External driving term is $F(n) = 2^n = 1 \cdot 2^n$ (base $s = 2$).
   • Notice that $s = 2$ is already a characteristic root with multiplicity $m = 2$!
   • Therefore, multiplying by $n^2$: $$a_n^{(p)} = A \cdot n^2 \cdot 2^n$$
   • Substitute $a_n^{(p)}$ into the recurrence: $$A n^2 2^n - 4 A (n - 1)^2 2^{n-1} + 4 A (n - 2)^2 2^{n-2} = 2^n$$
   • Divide through by $2^n$: $$A n^2 - 4 A (n - 1)^2 \left(\frac{1}{2}\right) + 4 A (n - 2)^2 \left(\frac{1}{4}\right) = 1$$ $$A [n^2 - 2(n^2 - 2n + 1) + (n^2 - 4n + 4)] = 1$$ $$A [n^2 - 2n^2 + 4n - 2 + n^2 - 4n + 4] = 1$$ $$A [2] = 1 \implies A = \frac{1}{2}$$
   • Thus: $$a_n^{(p)} = \frac{1}{2} n^2 2^n = n^2 2^{n-1}$$

3. Step 3: Form Total General Solution

   $$a_n = a_n^{(h)} + a_n^{(p)} = (\alpha_0 + \alpha_1 n) 2^n + \frac{1}{2} n^2 2^n$$

4. Step 4: Solve for Constants using Initial Conditions

   • For $n = 0$: $$a_0 = \alpha_0 \cdot 2^0 + 0 = 1 \implies \alpha_0 = 1$$
   • For $n = 1$: $$a_1 = (1 + \alpha_1) \cdot 2^1 + \frac{1}{2} (1)^2 \cdot 2^1 = 2 (1 + \alpha_1) + 1 = 2$$ $$2 + 2\alpha_1 + 1 = 2 \implies 2\alpha_1 = -1 \implies \alpha_1 = -\frac{1}{2}$$

5. Step 5: Final Unique Closed Form

   $$a_n = \left( 1 - \frac{1}{2} n \right) 2^n + \frac{1}{2} n^2 2^n = \left( 1 - \frac{n}{2} + \frac{n^2}{2} \right) 2^n$$

---

Example 3: Binary Strings with No Consecutive 1s

Problem Statement: Find the number of binary strings of length $n$ that do not contain two consecutive 1s (11).

Step-by-Step Solution:

1. Let $a_n$ denote the number of valid binary strings of length $n$.
2. Case Analysis on the Final Bit:
   • Case A (Ends in 0): The preceding $n - 1$ bits can be any valid binary string without 11. There are $a_{n-1}$ such strings.
   • Case B (Ends in 1): To avoid 11, the $(n-1)$-th bit MUST be 0. The preceding $n - 2$ bits can be any valid string. There are $a_{n-2}$ such strings.
3. By the Rule of Sum, we obtain the recurrence: $$a_n = a_{n-1} + a_{n-2} \quad \text{for } n \ge 3$$
4. Base Cases:
   • $n = 1$: Valid strings are 0 and 1 $\implies a_1 = 2$.
   • $n = 2$: Valid strings are 00, 01, 10 (11 forbidden) $\implies a_2 = 3$.
5. Comparing to the standard Fibonacci sequence $(F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, \dots)$: $$a_n = F_{n+2}$$

---

🎯 Exam & Interview Pitfall Check

Recurrence Form	Governing Characteristic / Trial Solution	Common Fatal Error
$a_n = c_1 a_{n-1} + c_2 a_{n-2}$	$r^2 - c_1 r - c_2 = 0$	Setting signs incorrectly: writing $r^2 + c_1 r + c_2 = 0$
Root $r$ repeats with multiplicity $m$	$(\alpha_0 + \alpha_1 n + \dots + \alpha_{m-1} n^{m-1}) r^n$	Writing $\alpha_0 r^n + \alpha_1 r^n$ (collapsing constants into one)
$F(n) = c \cdot s^n$ where $s$ is root of mult. $m$	$a_n^{(p)} = A \cdot n^m \cdot s^n$	Trying $A \cdot s^n$ (which evaluates to 0 on LHS due to resonance)
Applying Initial Conditions	Apply exclusively to $a_n = a_n^{(h)} + a_n^{(p)}$	Solving $\alpha_i$ using $a_n^{(h)}$ alone before adding $a_n^{(p)}$
Degree of Recurrence $k$	Requires strictly $k$ initial conditions	Attempting to solve unique closed form with fewer than $k$ values

Core Conceptual Questions

Question 1: If the characteristic equation has roots $r = 3, 3, 3$ (multiplicity 3), why must we multiply by ascending powers of $n$? Key Focus Points: Because root $3$ repeats three times, the functions $3^n, n 3^n, n^2 3^n$ form a linearly independent basis for the 3-dimensional solution space of the 3rd-order recurrence:

$$a_n = (\alpha_0 + \alpha_1 n + \alpha_2 n^2) \cdot 3^n$$

If you omit the $n$ and $n^2$ factors, the terms $\alpha_0 3^n + \alpha_1 3^n + \alpha_2 3^n = (\alpha_0 + \alpha_1 + \alpha_2) 3^n$ collapse into a single term with only 1 degree of freedom, failing to satisfy 3 independent initial conditions!

Question 2: What trial particular solution should be used if $F(n) = 2^n$ and $r = 2$ is already a simple root of the characteristic equation? Key Focus Points: Because $2$ is already a root of the homogeneous equation with multiplicity $m = 1$, the standard trial $A \cdot 2^n$ will produce $0$ when plugged into the left-hand side (resonance!). You must multiply by $n^1$:

$$a_n^{(p)} = A \cdot n \cdot 2^n$$

If $2$ had multiplicity 2, you would try $A \cdot n^2 \cdot 2^n$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Applying Initial Conditions to the Homogeneous Solution Alone Why it fails: In non-homogeneous recurrences $a_n = a_n^{(h)} + a_n^{(p)}$, calculating $\alpha_i$ using $a_n^{(h)}$ alone is completely incorrect! The boundary values must balance the entire expression: $a_0 = a_0^{(h)}(0) + a_0^{(p)}(0)$.

Trap 2: Forgetting the Degree Determines the Number of Initial Conditions Why it fails: A recurrence of degree $k$ strictly requires $k$ initial conditions. If fewer than $k$ conditions are given, the sequence is underdetermined and has infinitely many solutions.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic8.1 Counting Principles, Permutations, Combinations & Stars and BarsNext Topic →8.3 Ordinary Generating Functions & Closed-Form Combinatorial Sequences