Solving Linear Recurrence Relations

Welcome to your next lesson. In our previous discussions on graph theory, we analyzed the static structure of networks. Now, we transition to a dynamic perspective, exploring sequences and their growth patterns. This brings us to the topic of recurrence relations, a cornerstone of discrete mathematics that is fundamental to analyzing the efficiency of algorithms, a subject you've encountered throughout your Information Technology studies.

This lesson focuses on a specific, powerful technique for solving a class of recurrences frequently tested in the GATE exam: linear recurrence relations with constant coefficients. You will learn a systematic, algebraic method to find exact closed-form formulas for these sequences. We will cover both homogeneous relations (where terms only depend on previous terms) and non-homogeneous relations (which include an additional function). Mastering this will not only equip you for direct questions on this topic but also deepen your understanding of how recursive algorithm costs are calculated.

1. Homogeneous Recurrence Relations

A linear homogeneous recurrence relation with constant coefficients is an equation of the form:

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}

where the $c_{i}$ are constants. The Fibonacci sequence, $F_{n} = F_{n - 1} + F_{n - 2}$ , is a classic example.

Our goal is to find a closed-form solution, an explicit formula for $a_{n}$ that doesn't rely on previous terms. The method involves assuming a solution of the form $a_{n} = r^{n}$ and transforming the recurrence into an algebraic equation called the characteristic equation.

The following video provides an excellent walkthrough of this entire process.

HOMOGENEOUS RECURRENCE RELATIONS - Discrete Mathematics

This video from TrevTutor systematically demonstrates how to solve homogeneous recurrence relations. It covers forming the characteristic equation, finding its roots, constructing the solution, and using initial conditions.

Please watch the following segments carefully: Characteristic Equation (to polynomial): This part shows how to convert the recurrence relation into its corresponding characteristic polynomial. The key idea is to substitute a_n with r^n, a_{n-1} with r^{n-1}, and so on, and then simplify. General Solution (Distinct Roots) (to solution form): Once you have the polynomial, you find its roots (r_1, r_2, \dots). If the roots are distinct, the general solution takes the form a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \dots. Solving for Coefficients (to verify): The video then demonstrates the crucial final step: using the given initial conditions (e.g., a_0 and a_1) to create a system of linear equations and solve for the unknown constants (\alpha, \beta). Verification (the check): Watch how the derived formula is tested to ensure it generates the correct terms of the sequence.

Let's consolidate the steps from the video:

Write the Characteristic Equation: For a recurrence $a_{n} - c_{1} a_{n - 1} - c_{2} a_{n - 2} = 0$ , the equation is $r^{2} - c_{1} r - c_{2} = 0$ .
Find the Roots: Solve the polynomial to find the roots, $r_{1}, r_{2}$ .
Form the General Solution: If $r_{1} \neq = r_{2}$ , the solution is $a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n}$ .
Find the Constants: Use the initial conditions to solve for $α_{1}$ and $α_{2}$ .

What If the Roots Are Not Distinct?

A critical variation occurs when the characteristic equation has repeated roots. For example, if the equation is $(r - 2)^{2} = 0$ , the root $r = 2$ has a multiplicity of two. In this case, the general solution is modified.

If a root $r_{1}$ has multiplicity $k$ , its contribution to the solution is not just $α r_{1}^{n}$ , but a polynomial in $n$ multiplied by $r_{1}^{n}$ :

(α_{1} + α_{2} n + α_{3} n^{2} + \dots + α_{k} n^{k - 1}) r_{1}^{n}

For a second-order recurrence with a single root $r_{1}$ of multiplicity 2, the general solution becomes:

a_{n} = (α_{1} + α_{2} n) r_{1}^{n}

Let's see this in action.

HOMOGENEOUS RECURRENCE RELATIONS - Discrete Mathematics

The same video continues by explaining how to handle repeated roots, which is a common scenario in GATE problems.

Please watch these segments: Form for Repeated Roots (to n): This part explains why and how the form of the solution changes when you encounter repeated roots. The key takeaway is the multiplication by powers of n. Example with Repeated Roots (solving it): Follow the example of solving a recurrence with a repeated root, including finding the coefficients. General Summary (to next part): This final section provides a helpful summary of the solution forms for both distinct and repeated roots.

2. Non-Homogeneous Recurrence Relations

Now, let's consider relations of the form:

a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k} + f (n)

The term $f (n)$ makes this non-homogeneous. For example, $a_{n} = 2 a_{n - 1} + 3^{n}$ .

The strategy here is to break the problem into two parts. The total solution $a_{n}$ is the sum of two components:

The homogeneous solution, $a_{n}^{(h)}$ , which you find by solving the relation with $f (n)$ set to 0 (exactly as we did above).
The particular solution, $a_{n}^{(p)}$ , which is a specific solution that depends on the form of $f (n)$ .

a_{n} = a_{n}^{(h)} + a_{n}^{(p)}

The most challenging part is finding the particular solution $a_{n}^{(p)}$ . We use the "method of undetermined coefficients," which means we make an educated guess for the form of $a_{n}^{(p)}$ based on the form of $f (n)$ .

NON-HOMOGENEOUS RECURRENCE RELATIONS - Discrete Mathematics

The next video from TrevTutor explains this "sum of two solutions" strategy and provides the essential guide for guessing the particular solution.

Overall Strategy (to chart): Watch this introduction to understand the concept of splitting the solution into homogeneous and particular parts. Guessing the Particular Solution (the chart): Pay close attention to the chart presented. This table is your primary tool for determining the form of a_n^{(p)}. For GATE, the most common forms of f(n) are polynomials (e.g., a constant, n, or n^2) and exponentials (e.g., c^n).

Here's a summary of the common guesses:

If $f (n)$ is a polynomial of degree $k$ , guess $a_{n}^{(p)}$ as a full polynomial of degree $k$ .
- Example: if $f (n) = 3 n + 5$ , guess $a_{n}^{(p)} = A n + B$ .
If $f (n)$ is an exponential $c \cdot s^{n}$ , guess $a_{n}^{(p)}$ as $A \cdot s^{n}$ .
- Example: if $f (n) = 4 \cdot 3^{n}$ , guess $a_{n}^{(p)} = A \cdot 3^{n}$ .

The Complication: Overlap with the Homogeneous Solution

The method has one crucial exception. If your guess for $a_{n}^{(p)}$ is already a term in the homogeneous solution $a_{n}^{(h)}$ , you must modify your guess. You do this by multiplying your guess by $n$ . If that still results in a term in $a_{n}^{(h)}$ (which happens if the root is repeated), you multiply by $n^{2}$ , and so on.

This is the most frequently tested aspect of non-homogeneous recurrences. Let's watch a full example that deals with this exact scenario.

NON-HOMOGENEOUS RECURRENCE RELATIONS - Discrete Mathematics

This segment walks through a complete problem where the initial guess for the particular solution overlaps with the homogeneous solution, forcing a modification. Understanding this is key.

Watch the detailed example from this section. Trace these steps as the narrator works through the problem a_{n+1} - 2a_n = 2^n: He finds the homogeneous solution: a_n^{(h)} = \alpha \cdot 2^n. He considers the form of f(n)=2^n. The initial guess for the particular solution would be A \cdot 2^n. He notes this guess is of the same form as the homogeneous solution. He modifies the guess to a_n^{(p)} = A \cdot n \cdot 2^n. He substitutes this modified guess back into the original recurrence to solve for A. He forms the total solution a_n = \alpha \cdot 2^n + A \cdot n \cdot 2^n. Finally, he uses the initial condition (a_0=1) on the total solution to find \alpha.

Let's Solve a GATE-Style Problem

Let's apply this full procedure to a typical problem.

Problem: Find the solution for the recurrence relation $a_{n} - 6 a_{n - 1} + 9 a_{n - 2} = 4 \cdot 3^{n}$ for $n \geq 2$ , with initial conditions $a_{0} = 1$ and $a_{1} = 3$ .

Step 1: Solve the Homogeneous Part
The homogeneous relation is $a_{n} - 6 a_{n - 1} + 9 a_{n - 2} = 0$ .
The characteristic equation is $r^{2} - 6 r + 9 = 0$ , which is $(r - 3)^{2} = 0$ .
We have a repeated root: $r_{1} = r_{2} = 3$ .
So, the homogeneous solution is $a_{n}^{(h)} = (α_{1} + α_{2} n) \cdot 3^{n}$ .

Step 2: Find the Particular Solution
The non-homogeneous term is $f (n) = 4 \cdot 3^{n}$ .
Our initial guess for $a_{n}^{(p)}$ would be $A \cdot 3^{n}$ .
Check for overlap: The terms in our homogeneous solution are $α_{1} \cdot 3^{n}$ and $α_{2} \cdot n \cdot 3^{n}$ . Our guess $A \cdot 3^{n}$ overlaps. Let's try multiplying by $n$ . The new guess is $A \cdot n \cdot 3^{n}$ . This still overlaps.
So, we must multiply by $n$ again. Our final, correct guess is $a_{n}^{(p)} = A \cdot n^{2} \cdot 3^{n}$ .

Step 3: Solve for the Coefficient A
Substitute $a_{n} = A n^{2} 3^{n}$ into the original non-homogeneous recurrence:

A n^{2} 3^{n} - 6 [A (n - 1)^{2} 3^{n - 1}] + 9 [A (n - 2)^{2} 3^{n - 2}] = 4 \cdot 3^{n}

Divide the entire equation by $3^{n - 2}$ :

A n^{2} 3^{2} - 6 [A (n - 1)^{2} 3^{1}] + 9 [A (n - 2)^{2}] = 4 \cdot 3^{2}

9 A n^{2} - 18 A (n^{2} - 2 n + 1) + 9 A (n^{2} - 4 n + 4) = 36

Expanding this and collecting terms:

(9 A - 18 A + 9 A) n^{2} + (36 A - 36 A) n + (- 18 A + 36 A) = 36

The $n^{2}$ and $n$ terms cancel out, leaving:

18 A = 36 ⟹ A = 2

So, our particular solution is $a_{n}^{(p)} = 2 n^{2} 3^{n}$ .

Step 4: Combine and Use Initial Conditions
The total solution is $a_{n} = a_{n}^{(h)} + a_{n}^{(p)} = (α_{1} + α_{2} n) 3^{n} + 2 n^{2} 3^{n}$ .

Use $a_{0} = 1$ :

a_{0} = 1 = (α_{1} + α_{2} \cdot 0) 3^{0} + 2 \cdot 0^{2} \cdot 3^{0} ⟹ α_{1} = 1

Use $a_{1} = 3$ :

a_{1} = 3 = (α_{1} + α_{2} \cdot 1) 3^{1} + 2 \cdot 1^{2} \cdot 3^{1}

3 = (1 + α_{2}) \cdot 3 + 6

3 = 3 + 3 α_{2} + 6 ⟹ 3 α_{2} = - 6 ⟹ α_{2} = - 2

Final Solution:
Putting it all together, $a_{n} = (1 - 2 n) 3^{n} + 2 n^{2} 3^{n} = (1 - 2 n + 2 n^{2}) 3^{n}$ .

Conclusion

In this lesson, you have learned a robust, step-by-step method for solving linear recurrence relations with constant coefficients, a key skill for your GATE preparation.

Key Takeaways:

Homogeneous Solution: Convert the recurrence to its characteristic equation. The form of the solution depends on whether the roots are distinct or repeated. For repeated roots, you multiply by increasing powers of $n$ .
Non-Homogeneous Solution: The total solution is the sum of the homogeneous solution ( $a_{n}^{(h)}$ ) and a particular solution ( $a_{n}^{(p)}$ ).
Particular Solution: The form of $a_{n}^{(p)}$ is guessed based on the non-homogeneous term $f (n)$ .
The Overlap Rule: If your guess for $a_{n}^{(p)}$ is already part of $a_{n}^{(h)}$ , you must multiply the guess by $n$ until there is no overlap. This is a critical detail.
Finding Coefficients: The constants in the homogeneous part are found last, by applying the initial conditions to the complete solution $a_{n}^{(h)} + a_{n}^{(p)}$ .

The algebraic method we studied today is powerful but can be cumbersome. In our next lesson, we will explore Generating Functions. This is an even more powerful and elegant technique from discrete mathematics that can solve these recurrences and a much wider class of counting problems.