Recurrence Relations - Method of Summation Factors
There is another way of solving recurrence relations of the form , where , and are functions of , which some references call the method of summation factors. This method is pretty straightforward when and are linear functions of , and it solves several recurrence relations problems in recreational mathematics and computer science, among others.
Contents
Methodology
First, define a summation factor , which, when multiplied to the recurrence relation, gives
This summation factor must be chosen such that the "new" sequence of numbers has an term of and an term of . This factor is chosen to be
Thus, we can now let and . The recurrence relation now becomes
where can be thought of as the difference between the and the term. Thus, the closed form of is
where is a function of the index . But and . Therefore, the closed form of the original recurrence relation is
Example 1: The Tower of Hanoi Problem
Find the closed form of the recurrence relation , .
The summation factor with and is
where the 1's and 2's occur times each. Multiplying this to the recurrence relation gives
Let . Then and . So,
It follows that the closed form of is
Note that the summation above is a finite geometric series. But since , the closed form of is
Example 2: The Quicksort Algorithm
Find a closed form for the recurrence relation , .
Here and . The summation factor is thus
Again, there are factors each in the numerator and the denominator. Multiplying to the recurrence relation gives
by partial fraction decomposition. Now let , so that and . Hence,
from which the closed form of is given by
Note that the second summation on the RHS telescopes as
On the other hand, if we let be the harmonic number (the sum of the reciprocals of the first positive integers), we now write the first summation on the RHS as
Therefore,
Since , we now have the closed form of
If desired, we can rewrite . Since , we obtain
Example 3
Let be a function that satisfies the equation
for all nonnegative integers with . Find .
Rewriting the equation as
we see that and . Thus, the summation factor is
Multiplying to the recurrence relation gives
Let . Then and . Thus, the new recurrence relation becomes
and from this, we have the closed form of as
But . Therefore, the closed from of is
Example 4 (ongoing edit)
Let be a sequence of real numbers such that and
for all integers . Find the remainder when is divided by .
Problems