Example: {tn} and {un} (1 <= n) denote particular unspecified infinite sequences indexed by the same variable n. (1 <= n) indicates that n begins at 1 and increases without bound.
When we wish to be more specific we may list several terms of the sequence followed by ... indicating that the sequence continues indefinitely.
Example: {1, 3, 5, 7, 9, 11, 13, 15, ...} denotes a particular infinite sequence of numbers. The sequence appears to be the positive, odd numbers although we cannot be certain what the sequence actually is since, without a formula for the nth term, we can only extrapolate from the terms given.
The most precise method of specifying a sequence is to specify a formula for the nth term of the sequence.
Example: {2*n-1} (1<=n) denotes the positive odd numbers. We can see that letting n=1 produces 1, n=2 produces 3 and so on.
What are Recurrence Realtions?
Recurrence Relations are another means of defining a sequence of numbers. Recurrence relations define a term of the sequence in terms of previous terms of the sequence and, possibly, other functions of n.
Recurrence relations crop up in many disciplines. They are especially common in the study of Algorithms. However, even a concept as rudimentary as exponentiation can be expressed as a recurrence.
Example: Consider raising the non-negative number X to the non-negative integer power n.
We may define PwrX(0) = 1 and PwrX(n+1) = X*PwrX(n).
I.e., in standard algebraic notation, Xn+1 = X*Xn
More Examples
Factorial may be defined as a recurrence relation since
Fact(n+1) = (n+1)*Fact(n) and Fact(0) = 1
Also, the Fibonacci numbers may be defined by the recurrence relation,
Fibo(n+2) = Fibo(n+1) + Fibo(n), F(0) = 1, F(1) = 1
In plain english the above says that a fibonacci number is equal to the sum of the previous two fibonacci numbers.
Exercise: Use the formula above to compute the first 10 fibonacci numbers and confirm that they are the subsequence,
{0, 1, 1, 2, 3, 5, 8, 13, 21, 34}.
NOTE: We often see recurrence relations such as the Fibonacci sequence defined somewhat differently.
I.e. Fibo(n) = Fibo(n-1) + Fibo(n-2) where n is the highest index rather than the lowest.
Although, these two approaches are essentially equivalent there are some notational and pedagogical nuances that lead us to choose the former method.
Solving Recurrence Relations
Many techniques exist to solve specific types of recurrence relations. None have proven to provide a solution to all recurrence relations. Chapter 4 of your text book provides a number of methods. We will look at these and other methods.
Backward Substitution and Iteration
In this method we simply continue to substitute back until we see a pattern of some sort.
We then deduce a formula from the pattern.
Once we discover a likely formula we prove that the formula acually solves the relation.
Example:
T(n+1) = 2*T(n) and T(0) = 1
By substituting 2*T(n-1) for T(n) we have
T(n+1) = 4*T(n-1)
Continuing in this manner we have
T(n+1) = 2k+1*T(n-k)
Eventually k = n and we have
T(n+1) = 2n+1*T(0) = 2n+1
Of course this immedaitely implies that T(n) = 2n
Perhaps a good way of thinking of this method is that we continue to substitute for T(i) in terms of T(j) where j<i until all the T terms have been reduced to a base case.
Admittedly this is an extremely simple example. It was only intended to illustrate the method.
Example:
Solve the following recurrence using iteration.
T(n) = 2*T(n/2) + n and T(1) = 1
Since T(n/2) = 2*T(n/4) + n/2 we have
T(n) = 2*(2*T(n/4) + n/2)) + n = 4*T(n/4) + 2*n
substituting for T(n/4) we obtain
T(n) = 4*(2*T(n/8) + n/4)) + 2*n = 8*T(n/8) + 3*n
Continuing in this manner we find that
T(n) = 2k*T(n/2k) + k*n
After log2(n) substitutions we have
T(n) = 2log2(n)*T(n/2log2(n)) + log2(n)*n
Noting that 2log2(n) = n we have
T(n) = n + n*log2(n)
Your text has many more challenging examples.
Forward Substitution and Iteration
This method is probably the most staightforward and should be the first that we try. Here we simply generate successive terms and hope to recognize a formula. Then we prove that the formula is correct.
Example:
T(n+1) = 2*T(n) + 1 and T(0) = 0
T(1) = 1
T(2) = 3
T(3) = 7
T(4) = 15
T(5) = 31
The obvious guess here, T(n) = 2n - 1, turns out to be the correct guess.
We may easily prove the result using mathematical induction.
Special Polynomial Relations
If the difference of consecutive terms of a recurrence is an nth degree polynomial then the recurrence solution is an n+1 degree polynomial.
Example:
T(n+1) - T(n) = 3*n3-5*n
The solution to T(n) must be a 4th degree polynomial. The exact coefficients depend upon the initial conditions for T(n).
Change of Variable
Some recurrence relations (often ones that look difficult) can be solved fairly easily by a change of variables.
Consider the following relation.
T(n) = 2*T(n/2) + n and T(1) = 1.
Note that the above relation can only be computed when n is a power of two.
I.e., we can only compute T(1), T(2), T(4), T(8), etc.
Let m = log(n). Then, n = 2m
Consider another recurrence relation, S, such that S(m) = T(2m).
Then T(1) = S(0), T(2) = S(1), T(4) = S(2), T(8) = S(3), etc.
Now we have a relation in S(m) that is equivalent to the T(n) relation above. It is the following.
S(m) = 2*S(m-1) + 2m and S(0) = 1
The Master Method
The "Master Method" provides a cookbook method for solving recurrences of the form
T(n) = a*T(n/b) + f(n)
where a>=1 and b>1 are constants and f(n) is an asymptotically positive function. The Master Method has three distinct subcases given in your text (Cormen, Leiserson and Rivest) on page 62.
Finding the Sum of Geometric Series
Before looking at a very powerful method of solving recurrence relations we shall temporarily divert our attention to finding the sum of geometric series.
A geometric series is a (possibly infinite) sum of numbers where the nth number of the series is a constant multiple of the n-1 number in the series. The constant is always the same regardless of n.
For example, 1/2 + 1/4 + 1/8 + ... is an infinite geometric series where the constant multiplier is 1/2.
Such infinite geometric series may be solved by employing a clever trick.
Example: Let us consider the infinite series 3/5 + 9/25 + 27/125 + 81/625 + ...
The ratio, r, between any two consecutive terms is 3/5.
Let the sum of the series be S = 3/5 + 9/25 + 27/125 + 81/625 + ...
Now multiply both sides by 3/5 obtaining (3/5)*S = 9/25 + 27/125 + 81/625 + ...
Subtracting the second equality from the first and combining like terms yields the following:
S - (3/5)*S = (2/5)S = 3/5 (Note that nearly all terms on the right cancel).
Thus we see that the sum, S = (5/2)(3/5) = 3/2
The "trick" to this approach lies in the fact that multiplying by r effectively shifts the elements of the sum one position.
In a similar fashion we can find a formula for the sum of any infinite geometric series.
Example: Let the sum of an arbitrary infinite series, S = a + a*r + a*r2 + a*r3 + ...
where r is the ratio between successive terms. (Note: if r >= 1 then the sum is, obviously, infinite.)
Then r*S = a*r + a*r2 + a*r3 + ...
Again, subtracting the second equality from the first and combining like terms yields the following:
S - r*S = a
Therefore, S*(1 - r) = a and S = a/(1 - r).
It is important to note that we multiplied the entire sum by a constant (without combining any terms) and obtained another sum that was the first sum shifted by one element. This approach is the key to solving many recurrence relations.
Solving Recurrence Relations using Annihilators
Consider the same simple recurrence relation we solved earlier T(n) = 2*T(n)
This notation specifies that the n+1st term of the sequence is twice the previous (nth) term.
In order to specify the entire sequence we must, of course, specify a starting point such as T(0) = 1.
As we determined earlier from these two equalities we have
T(0) = 1, T(1) = 2, T(2) = 4, T(3) = 8, etc. yielding the sequence {1, 2, 4, 8, 16, ...}
and we know that T(n) = 2n (0<=n)
As specified earlier we can let {tn} denote the entire sequence {1, 2, 4, 8, 16, ...}.
Consider now the result of substituting n+1 for n yielding a new sequence defined by 2n+1 (0<=n) giving
{2, 4, 8, 16, 32, ...}
This is precisely the sequence {tn} = {1, 2, 4, 8, 16, ...} shifted left by one element.
We let S denote the left shift operator so that when S is applied to {tn} we produce {tn+1}.
Thus, {tn+1} = S({tn})
Note now that if we multiply (each term of) {tn} by 2 we produce {tn+1}.
This means that S({tn}) = 2*{tn} and we have
S({tn}) - 2*{tn} = 0
Although it may appear to be an abuse of notation we may "factor out" {tn} obtaining
(S - 2){tn} = 0
When there is no confusion we may drop the braces around the sequence and obtain
(S - 2)tn = 0
Thus, with the notational conversion specified above the recurrence T(n+1) = 2*T(n) becomes
(S - 2)tn = 0.
We now state, without proof, that the solution to any recurrence that can be notationally converted to the form
(S - C)(tn) = 0 is tn = t0*Cn (where C is a constant) and (0<=n).
This is actually very easily proven simply by using the forward substitution method.
Let us now consider a more complex example.
T(n+2) = 2*T(n+1) - T(n) is equivalent to T(n+2) - 2*T(n+1) + T(n) = 0
Using the notational conversion given above we now have the following:
(S2 - 2*S + 1)tn = 0
where S2 denotes the application of the shift operator twice and 2*S denotes the result of shifting the sequence once to the left and then multiplying the resulting sequence by 2.
Next, we apply ordinary algebra as if the above were a simple algebraic expression and obtain the following.
(S - 1)2tn = 0
Although the notion of such algebraic manipulation may not seem to be altogether justified proper analysis (not given here) does demonstrate the correctness of this method.
With the above as background we are now ready to state some very powerful results for solving recurrence relations.
Theorem 1. A recurrence of the form
(S - C)Ktn = 0 has as its solution
tn = Cn*P(n, k-1) where P is a polynomial in n of degree <= k-1.
Theorem 2. A recurrence of the form
(S - C)tn = g(n) has as its solution
tn = Cn*t0 + SUM(Cn-i*g(i)) (where 1 <= i <= n)
Theorem 3. A recurrence of the form
(S - C1)k1(S - C2)k2tn = 0 has as its solution the sum of the solutions of (S - C1)k1tn = 0 and (S - C2)k2tn = 0
It is important to note here that C1 and C2 must not be equal. For a discussion on this see "Applying Multiple Shift Functions" below.
Example: Consider the relation T(n+2) - 3*T(n+1) +2*T(n) = 0
Applying the notational conversion we learned above we have the following.
(S2 - 3*S + 2)tn = 0. This factors into the following:
(S - 2)(S - 1)tn = 0
The solution to (S - 1)tn = 0 is C1 (a constant sequence).
And the solution to (S - 2)tn = 0 is 2n*C2
Therefore the solution to (S - 2)(S - 1)tn = 0 is C1 + 2n*C2
Example - solving the Fibonacci numbers:
The Fibonacci numbers are defined as follows:
tn+2 = tn+1 + tn, t0=0 and t1 = 1
This yields the following:
S2 - S - 1 = 0
Using the quadratic equation we may factor this into
(S - r1)(S - r2) = 0 where r1 = (1 + sqrt(5))/2 and r2 = (1 - sqrt(5))/2
Employing Theorems 1 and 3 above we obtain the solution
tn = C1*r1n + C2*r2n
Using the facts t0= 0 and t1 = 1 we find that
C1 = sqrt(5)/5 and C2 = -sqrt(5)/5
Example:
Solve the recurrence relation tn+2 = 2*tn+1 +3*tn, t0=0 and t1=1
(S2 - 2*S - 3)tn = 0
(S - 3)(S + 1)tn = (S - 3)(S - (-1))tn = 0
Therefore tn = A*3n + (-1)n*B
Applying the initial conditions we find that a = 1/4 and B = -1/4.
Exercise:
Write a program to verify that the above solution is correct. Do this by computing the first 25 Fibonacci numbers both by the formula given above and iteratively using the recurrence relation.
In all of our examples thus far, after our notational conversion, the right side of our equation has always been equal to zero. Let us now consider a case where the right side of the equation is a nonzero function.
Example:
Solve the recurrence relation tn+1 = tn + n + 1
Equivalently tn+1 - tn = n + 1 yielding
(S - 1)tn = n + 1
Now, n + 1 is a polynomial in n of degree k - 1 where k = 2.
Therefore, by Theorem 1, n + 1 is a solution to (S-1)2.
Let's now apply (S - 1)2 to both sides of the original equation obtaining
(S - 1)(S-1)2tn = (S-1)2(n + 1) = 0 (since n + 1 is a solution to (S-1)2tn = 0)
Now, (S-1)(S-1)2tn = (S-1)3tn = 0 and by Theorem 1 its solution is
Cn*P(n , k-1) = Cn*(a1*n2 + a2*n + a3) where a1, a2 and a3 are constants.
Exercise:
Solve the recurrence relation tn+2 = 2*tn+1 + tn, t0 = 0 and t1 = 1
Exercise:
Solve the recurrence relation tn+1 = 2*tn + a*n + b
Exercise:
Solve the recurrence relation tn+2 = 2*tn+1 - tn, t0 = 0 and t1 = 1
Applying Multiple Shift Functions
Although the methods given above find correct solutions to recurrence relations some caution must be exercised in applying the methods blindly since there are some important nuances in the theory behind the methods and the theory has not been covered here.
Example:
If we apply Theorem 3 blindly to the converted recurrence relation (S - 1)(S - 1)tn = 0 we might be tempted to conclude that since the solution of (S - 1)tn = 0 is a constant that the solution to the recurrence above is the sum of two constants which is, of course, another constant.
Even though a constant is a solution it is not the most general. In fact we are misapplying Theorem 3 because C1 = C2.
Let (S - 1)tn = unwhere tn is some arbitrary sequence.
Then (S - 1)(S - 1)tn = (S - 1)un
and if un is a constant then tn is a solution to (S - 1)(S - 1)tn = 0.
Therefore the solution to (S - 1)un = a is also a solution to (S - 1)(S - 1)tn = 0.
As it turns out a*n + b is a solution to (S - 1)un = a and thus
a*n + b is also a solution to (S - 1)(S - 1)tn = 0 supporting Theorem 1.
More generally, let F1 and F2 be Shift operator functions.
Let un be the solution to (F1)un = 0.
Then the solution to (F2)tn = un is also a solution to
(F1oF2)tn = 0
A Coarse Method of Determining Order of Complexity
One may determine the "approximate" order of complexity of a function by examining the ratio of the Nth term compared to the N+1st term. I.e., if F is a recurrence relation then examine F(N+1) compared to F(N) as N grows. Of course this ratio tends to infinity since growth functions are normally monotonically increasing but one may make a more discriminating comparison by computing a function that the ratio tends to.Polynomials
Example:
Consider f(n) = n2
f(n+1)/f(n) = (n2 + 2n + 1)/n2 = 1 + 2/n + 1/n2
Since 2/n and 1/n2 both tend to 0 as n tends to infinity f(n+1)/f(n) tends to f(n) = 1.
Note: The ratio is not any constant but specifically the constant one.
It is not difficult to show that all polynomials have this property. I.e. if f(n) is a polynomial then f(n+1)/f(n) tends to 1.
An interesting problem is to determine the converse. I.e. if f(n+1)/f(n) tends to one then is f(n) of polynomial order?
Other functions have interesting characteristics as well.
Constant Exponentials
Consider functions of the form f(n) = Cn.
In this case f(n+1)/f(n) = Cn+1/Cn = C (a constant).
Factorial
The ratio for the very common function, n!, is easy to compute.
f(n+1)/f(n) = (n+1)!/n! = n.
nn
Another interesting function is nn.
f(n+1)/f(n) = (n+1)n+1/nn = ((n+1)n(n+1))/nn = ((n+1)/n)n(n+1) = (1 + 1/n)n(n+1)
As n gets becomes large (1 + 1/n)n approaches e.
And so the ratio, (n+1)n+1/nn approaches en+e which approximately equals en.
Beyond nn
You may wish to consider what other functions give rise to ratios like Cn and which produce greater ratios such as n2.
Top of this page
Home page 
