## B.2 Solving Recurrences Using the Characteristic Equation
We develop a technique for determining the solutions to a large class of recurrences.
### B.2.1 Homogeneous Linear Recurrences
Definition A recurrence of the form
where *k* and the *ai* terms are constants, is called a ***homogeneous linear recurrence equation with constant coefficients.***
Such a recurrence is called "linear" because every term *ti* appears only to the first power. That is, there are no terms such as *t2n–i*, *tn–itn–j*, and so on. However, there is the additional requirement that there be no terms *tc(n–i)*, where *c* is a positive constant other than 1. For example, there may not be terms such as *tn/2*, *t*3(n–4), etc. Such a recurrence is called "homogeneous" because the linear combination of the terms is equal to 0.
Example B.4****The following are homogeneous linear recurrence equations with constant co-efficients:
****
Example B.5****The Fibonacci sequence, which is discussed in [Subsection 1.2.2](LiB0009.html#43), is defined as follows:
If we subtract *tn*–1 and t*n*–2 from both sides, we get
which shows that the Fibonacci sequence is defined by a homogeneous linear recurrence.
Next we show how to solve a homogeneous linear recurrence.
****
Example B.6****Suppose we have the recurrence
Notice that if we set
then
Therefore, *tn* = *rn* is a solution to the recurrence if *r* is a root of
Because
the roots are *r* = 0, and the roots of
****
These roots can be found by factoring:
The roots are *r* = 3 and *r* = 2. Therefore,
are all solutions to the recurrence. We verify this for 3*n* by substituting it into the left side of the recurrence, as follows:
With this substitution, the left side becomes
which means that 3*n* is a solution to the recurrence.
We have found three solutions to the recurrence, but we have more solutions, because if 3*n* and 2*n* are solutions, then so is
where *c*1 and *c*2 are arbitrary constants. This result is obtained in the exercises. Although we do not show it here, it is possible to show that these are the only solutions. This expression is therefore the general solution to the recurrence. (By taking *c*1 = *c*2 = 0, the trivial solution *tn* = 0 is included in this general solution.) We have an infinite number of solutions, but which one is the answer to our problem? This is determined by the initial conditions. Recall that we had the initial conditions
These two conditions determine unique values of *c*1 and *c*2 as follows. If we apply the general solution to each of them, we get the following two equations in two unknowns:
These two equations simplify to
The solution to this system of equations is *c*1 = 1 and *c*2 = −1. Therefore, the solution to our recurrence is
If we had different initial conditions in the preceding example, we would get a different solution. A recurrence actually represents a class of functions, one for each different assignment of initial conditions. Let's see what function we get if we use the initial conditions
with the recurrence given in [Example B.6](#ap-bex7). Applying the general solution in [Example B.6](#ap-bex7) to each of these conditions yields
These two equations simplify to
The solution to this system is *c*1 = 0 and *c*2 = 1. Therefore, the solution to the recurrence with these initial conditions is
[Equation B.1](#ap-beqn01) in [Example B.6](#ap-bex7) is called the characteristic equation for the recurrence. In general, this equation is defined as follows.
Definition The ***characteristic equation*** for the homogenous linear recurrence equation with constant coefficients
is defined as
The value of *r0* is simply 1. We write the term as *r0* to show the relationship between the characteristic equation and the recurrence.
Example B.7****The characteristic equation for the recurrence appears below it:
We use an arrow to show that the order of the characteristic equation is *k* (in this case, 2).
****
The steps used to obtain the solution in [Example B.6](#ap-bex7) can be generalized into a theorem. To solve a homogeneous linear recurrence with constant coefficients, we need only refer to the theorem. The theorem follows, and its proof appears near the end of this appendix.
Theorem B.1****Let the homogeneous linear recurrence equation with constant coefficients
be given. If its characteristic equation
has *k* distinct solutions *r*1, *r*2, …, *rk*, then the only solutions to the recurrence are
where the *ci* terms are arbitrary constants.
****
The values of the *k* constants *ci* are determined by the initial conditions. We need *k* initial conditions to uniquely determine *k* constants. The method for determining the values of the constants is demonstrated in the following examples.
Example B.8****We solve the recurrence
1. Obtain the characteristic equation:
2. Solve the characteristic equation:
The roots are *r* = 4 and *r* = −1.
3. Apply [Theorem B.1](#ap-bex9) to get the general solution to the recurrence:
4. Determine the values of the constants by applying the general solution to the initial conditions:
These values simplify to
The solution to this system is *c*1 = 1/5 and *c*2 = −1/5.
5. Substitute the constants into the general solution to obtain the particular solution:
****
Example B.9****We solve the recurrence that generates the Fibonacci sequence:
1. Obtain the characteristic equation:
2. Solve the characteristic equation:
From the formula for the solution to a quadratic equation, the roots of this characteristic equation are
3. Apply [Theorem B.1](#ap-bex9) to get the general solution to the recurrence:
4. Determine the values of the constants by applying the general solution to the initial conditions:
These equations simplify to
Solving this system yields 
5. Substitute the constants into the general solution to obtain the particular solution:
****
Although [Example B.9](#ap-bex11) provides an explicit formula for the *n*th Fibonacci term, it has little practical value, because the degree of precision necessary to represent  increases as *n* increases.
[Theorem B.1](#ap-bex9) requires that all *k* roots of the characteristic equation be distinct. The theorem does not allow a characteristic equation of the following form:
Because the term *r* − 2 is raised to the third power, 2 is called a ***root of multiplicity 3*** of the equation. The following theorem allows for a root to have a multiplicity. The proof of the theorem appears near the end of this appendix.
Theorem B.2****Let *r* be a root of multiplicity *m* of the characteristic equation for a homogeneous linear recurrence with constant coefficients. Then
are all solutions to the recurrence. Therefore, a term for each of these solutions is included in the general solution (as given in [Theorem B.1](#ap-bex9)) to the recurrence.
****
Example applications of this theorem follow.
Example B.10****We solve the recurrence
1. Obtain the characteristic equation:
2. Solve the characteristic equation:
The roots are *r* = 1 and *r* = 3, and *r* = 3 is a root of multiplicity 2.
3. Apply [Theorem B.2](#ap-bex12) to get the general solution to the recurrence:
We have included terms for 3*n* and *n*3*n* because 3 is a root of multiplicity 2.
4. Determine the values of the constants by applying the general solution to the initial conditions:
These values simply to
Solving this system yields *c*1 = −1, *c*2 = 1, and *c*3 = ⅓
5. Substitute the constants into the general solution to obtain the particular solution:
****
Example B.11****We solve the recurrence
1. Obtain the characteristic equation:
2. Solve the characteristic equation:
The roots are *r* = 3 and *r* = 1, and the root 1 has multiplicity 2.
3. Apply [Theorem B.2](#ap-bex12) to obtain the general solution to the recurrence:
4. Determine the values of the constants by applying the general solution to the initial conditions:
These equations simplify to
Solving this system yields *c*1 = 0, *c*2 = 1, and *c*3 = 1.
5. Substitute the constants into the general solution to obtain the particular solution:
****
### B.2.2 Nonhomogeneous Linear Recurrences
Definition A recurrence of the form
where *k* and the *ai* terms are constant and *f(n)* is a function other than the zero function, is called a ***nonhomogeneous linear recurrence equation with constant coefficients***.
By the zero function, we mean the function *f*(*n*) = 0. If we used the zero function, we would have a homogeneous linear recurrence equation. There is no known general method for solving a nonhomogeneous linear recurrence equation. We develop a method for solving the common special case
where *b* is a constant and *p(n)* is a polynomial in *n*.
Example B.12****The recurrence
is an example of Recurrence B.2 in which *k* = 1, *b* = 4, and *p(n)* = 1.
****
Example B.13****The recurrence
is an example of Recurrence B.2 in which *k*=1, *b*=4, and *p*(*n*)= 8*n*+7.
****
The special case shown in Recurrence B.2 can be solved by transforming it into a homogeneous linear recurrence. The next sample illustrates how this is done.
Example B.14****We solve the recurrence
The recurrence is not homogeneous because of term 4*n* on the right. We can get rid of that term as follows:
1. Replace *n* with *n*–1 in the original recurrence so that the recurrence is expressed with 4*n*–1 on the right:
2. Divide the original recurrence by 4 so that the recurrence is expressed in another way with 4*n*–1 on the right:
3. Our original recurrence must have the same solutions as these versions of it. Therefore, it must also have the same solutions as their differnce. This means we can get rid of the term 4*n*–1 by substracting the recurrence obtained in Step 1 from the recurrence obtained in Step 2. The result is
We can multiply by 4 to get rid of the fractions:
This is a homogeneous linear recurrence equation, which means that it can be solved by applying [Theorem B.1](#ap-bex9). That is, we solve the characteristic equation
obtain the general solution
and use the initial conditions *t*o = 0 and *t*1 = 4 to determine the particular solution:
****
In [Example B.14](#ap-bex17), the general solution has the terms
The first term comes from the characteristic equation that would be obtained if the recurrence were homogeneous, whereas the second term comes from the nonhomogeneous part of the recurrence—namely, *b*. The polynomial *p(n)* in this example equals 1. When this is not the case, the manipulations necessary to transform the recurrence into a homogeneous one are more complex. However, the outcome is simply to give *b* a multiplicity in the characteristic equation for the resultant homogeneous linear recurrence. This result is given in the theorem that follows. The theorem is stated without proof. The proof would follow steps similar to those in [Example B.14](#ap-bex17).
Theorem B.3****A nonhomogeneous linear recurrence of the form
can be transformed into a homogeneous linear recurrence that has the characteristic equation
where *d* is the degree of *p(n)*. Notice that the characteristic equation is composed of two parts:
1. The characteristic equation for the corresponding homogeneous recurrence
2. A term obtained from the nonhomogeneous part of the recurrence
If there is more than one term like *b**n**p(n)* on the right side, each one contributes a term to the characteristic equation.
****
Before applying this theorem, we recall that the degree of a polynomial *p(n)* is the highest power of *n*. For example,
Now let's apply [Theorem B.3](#ap-bex18).
Example B.15****We solve the recurrence
1. Obtain the characteristic equation for the corresponding homogeneous equation:
2. Obtain a term from the nonhomogeneous part of the recurrence:
The term from the nonhomogeneous part is
3. Apply [Theorem B.3](#ap-bex18) to obtain the characteristic equation from the terms obtained in Steps 1 and 2. The characteristic equation is
After obtaining the characteristic equation, proceed exactly as in the linear homogeneous case:
4. Solve the characteristic equation:
The roots are *r* = 3, and the root *r* = 4 has multiplicity 2.
5. Apply [Theorem B.2](#ap-bex12) to get the general solution to the recurrence:
We have three unknows, but only two initial conditions. In this case we must find another initial condition by computing the value of the recurrence at the next-largest value of *n*. In this case, that value is 2. Because
and *t*1 = 12,
In the exercises you are asked to (6) determine the values of the constants and (7) substitute the constants into the general solution to obtain
****
Example B.16****We solve the recurrence
1. Obtain the characteristic equation for the corresponding homogeneous recurrence:
2. Obtain a term from the nonhomogeneous part of the recurrence:
The term is
3. Apply [Theorem B.3](#ap-bex18) to obtain the characteristic equation from the terms obtained in Steps 1 and 2. The characteristic equation is
4. Solve the characteristic equation:
The root is *r* = 1, and it has a multiplicity of 3.
5. Apply [Theorem B.2](#ap-bex12) to get the general solution to the recurrence:
We need two more initial conditions:
In the excercise you are asked to (6) determine the values of the constants and (7) substitute the constants into the general solution to obtain
****
Example B.17****We solve the recurrence
1. Determine the characteristic equation for the corresponding homogeneous recurrence:
2. This is a case in which there are two terms on the right. As [Theorem B.3](#ap-bex18) states, each term contributes to the characteristic equation, as follows:
The two terms are
3. Apply [Theorem B.3](#ap-bex18) to obtain the characteristic equation from all the terms:
You are asked to complete this problem in the exercises.
****
### B.2.3 Change of Variables (Domain Transformations)
Sometimes a recurrence that is not in the form that can be solved by applying [Theorem B.3](#ap-bex18) can be solved by performing a change of variables to transform it into a new recurrence that is in that form. The technique is illustrated in the following examples. In these examples, we use *T*(*n*) for the original recurrence, because *t**k* is used for the new recurrence. The notation *T*(*n*) means the same things as *t**n*—namely, that a unique number is associated with each value of *n*.
Example B.18****We solve the recurrence
Recall that we already solved this recurrence using induction in [Section B.1](LiB0102.html#1371). We solve it again to illustrate the ***change of variables*** technique. The recurrence is not in the form that can be solved by applying [Theorem B.3](#ap-bex18) because of the term *n*/2. We can transform it into a recurrence that is in that form as follows. First, set
Second, substitute 2*k* for *n* in the recurrence to obtain
Next, set
in Recurrence B.3 to obtain the new recurrence,
This new recurrence is in the form that can be solved by applying [Theorem B.3](#ap-bex18). Therefore, applying that theorem, we can determine its general solution to be
This general solution to our original recurrence can now be obtained with the following two steps:
1. Substitute *T*(2*k*) for *t**k* in the general solution to the new recurrence:
2. Substitute *n* for 2*k* and lg *n* for *k* in the equation in Step 1:
Once we have the general solution to our original recurrence, we proceed as usual. That is, we use the initial condition *T*(1) = 1, determine a second initial condition, and then compute the values of the constants to obtain
****
Example B.19****We solve the recurrence
Recall that we were unable to solve this recurrence using induction in [Example B.3](LiB0102.html#1378). We solve it here with a change of variables. First, substitute 2*k* for *n* to yield
Next, set
in this equation to obtain
Apply [Theorem B.3](#ap-bex18) to this new recurrence to obtain
Perform the steps that give the general solution to the original recurrence:
1. Substitute *T*(2*k*) for *t**k* in the general solution to the new recurrence:
2. Substitute *n* for 2*k* and lg *n* for *k* in the equation obtained in Step 1:
Now proceed as usual. That is, use the initial condition *T*(1) = 0, determine two more initial conditions, and then compute the values of the constants. The solution is
****
Example B.20****We solve the recurrence
Substitute 2*k* for *n* in the recurrence to yield
Set
in Recurrence (B.4) to obtain
This recurrence does not look exactly like the kind required in [Theorem B.3](#ap-bex18), but we can make it look like that as follows:
Now apply [Theorem B.3](#ap-bex18) to this new recurrence to obtain
Perform the steps that give the general solution to the original recurrence:
1. Substitute *T*(2*k*) for *t**k* in the general solution to *t**k*:
2. Substitute *n* for 2*k* and lg *n* for *k* in the equation obtained in Step 1:
Use the initial condition *T*(1) = 0, determine a second initial condition, and then compute the values of the constants. The solution is
****
- Table of Contents
- BackCover
- Foundations of Algorithms Using C++ Pseudocode, Third Edition
- Preface
- Chapter Contents
- Pedagogy
- Course Outlines
- Acknowledgments
- Errors
- Chapter 1: Algorithms - Efficiency, Analysis, and Order
- 1.2 The Importance of Developing Efficient Algorithms
- 1.3 Analysis of Algorithms
- 1.4 Order
- 1.5 Outline of This Book
- Exercises
- Chapter 2: Divide-and-Conquer
- 2.1 Binary Search
- 2.2 Mergesort
- 2.3 The Divide-and-Conquer Approach
- 2.4 Quicksort (Partition Exchange Sort)
- 2.5 Strassen's Matrix Multiplication Algorithm
- 2.6 Arithmetic with Large Integers
- 2.7 Determining Thresholds
- 2.8 When Not to Use Divide-and-Conquer
- Exercises
- Chapter 3: Dynamic Programming
- 3.1 The Binomial Coefficient
- 3.2 Floyd's Algorithm for Shortest Paths
- 3.3 Dynamic Programming and Optimization Problems
- 3.4 Chained Matrix Multiplication
- 3.5 Optimal Binary Search Trees
- 3.6 The Traveling Salesperson Problem
- Exercises
- Chapter 4: The Greedy Approach
- 4.1 Minimum Spanning Trees
- 4.2 Dijkstra's Algorithm for Single-Source Shortest Paths
- 4.3 Scheduling
- 4.4 Huffman Code
- 4.5 The Greedy Approach versus Dynamic Programming: The Knapsack Problem
- Exercises
- Chapter 5: Backtracking
- 5.2 The n-Queens Problem
- 5.3 Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm
- 5.4 The Sum-of-Subsets Problem
- 5.5 Graph Coloring
- 5.6 The Hamiltonian Circuits Problem
- 5.7 The 0-1 Knapsack Problem
- Exercises
- Chapter 6: Branch-and-Bound
- 6.1 Illustrating Branch-and-Bound with the 0 - 1 Knapsack problem
- 6.2 The Traveling Salesperson Problem
- 6.3 Abductive Inference (Diagnosis)
- Exercises
- Chapter 7: Introduction to Computational Complexity - The Sorting Problem
- 7.2 Insertion Sort and Selection Sort
- 7.3 Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison
- 7.4 Mergesort Revisited
- 7.5 Quicksort Revisited
- 7.6 Heapsort
- 7.6.1 Heaps and Basic Heap Routines
- 7.6.2 An Implementation of Heapsort
- 7.7 Comparison of Mergesort, Quicksort, and Heapsort
- 7.8 Lower Bounds for Sorting Only by Comparison of Keys
- 7.8.1 Decision Trees for Sorting Algorithms
- 7.8.2 Lower Bounds for Worst-Case Behavior
- 7.8.3 Lower Bounds for Average-Case Behavior
- 7.9 Sorting by Distribution (Radix Sort)
- Exercises
- Chapter 8: More Computational Complexity - The Searching Problem
- 8.1 Lower Bounds for Searching Only by Comparisons of Keys
- 8.2 Interpolation Search
- 8.3 Searching in Trees
- 8.4 Hashing
- 8.5 The Selection Problem: Introduction to Adversary Arguments
- Exercises
- Chapter 9: Computational Complexity and Interactability - An Introduction to the Theory of NP
- 9.2 Input Size Revisited
- 9.3 The Three General Problem Categories
- 9.4 The Theory of NP
- 9.5 Handling NP-Hard Problems
- Exercises
- Chapter 10: Number-Theoretic Algorithms
- 10.1 Number Theory Review
- 10.2 Computing the Greatest Common Divisor
- 10.3 Modular Arithmetic Review
- 10.4 Solving Modular Linear Equations
- 10.5 Computing Modular Powers
- 10.6 Finding Large Prime Numbers
- 10.7 The RSA Public-Key Cryptosystem
- Exercises
- Chapter 11: Introduction to Parallel Algorithms
- 11.1 Parallel Architectures
- 11.2 The PRAM Model
- Exercises
- Appendix A: Review of Necessary Mathematics
- A.2 Functions
- A.3 Mathematical Induction
- A.4 Theorems and Lemmas
- A.5 Logarithms
- A.6 Sets
- A.7 Permutations and Combinations
- A.8 Probability
- Exercises
- Appendix B: Solving Recurrence Equations - With Applications to Analysis of Recursive Algorithms
- B.2 Solving Recurrences Using the Characteristic Equation
- B.3 Solving Recurrences by Substitution
- B.4 Extending Results for n, a Power of a Positive Constant b, to n in General
- B.5 Proofs of Theorems
- Exercises
- Appendix C: Data Structures for Disjoint Sets
- References
- Index
- Index_B
- Index_C
- Index_D
- Index_E
- Index_F
- Index_G
- Index_H
- Index_I
- Index_J
- Index_K
- Index_L
- Index_M
- Index_N
- Index_O
- Index_P
- Index_Q
- Index_R
- Index_S
- Index_T
- Index_U
- Index_V
- Index_W-X
- Index_Y
- Index_Z
- List of Figures
- List of Tables
- List of Algorithms, Examples, and Theorems
- List of Sidebars