notes11 notes22 notes33 notes44 notes55 notes66 notes77 notes88 notes99 notes1010 notes1111 notes1212 notes1313 notes1414 notes1515 notes1616 notes1717 notes1818 notes1919 notes2020 notes2121 notes2222 notes2323 notes2424 notes2525 notes2626 Massachusetts Institute of Technology Lecture ?? 6.042J/18.062J: Mathematics for Computer Science 19 Oct 00 Professors David Karger and Nancy Lynch

Lecture Notes

This lecture is about solving recurrences and recurrent problems. Needless to say, recurrent problems come up again and again. In particular, recurrences often arise in the analysis of recursive algorithms.

1 The Towers of Hanoi

In the Towers of Hanoi problem, there are three posts and seven disks of different sizes. Each disk has a hole through the center so that it fits on a post. At the start, all seven disks are on one post as shown in Figure ??. The disks are arranged by size so that the smallest is on top and the largest is on the bottom. The goal is to end up with all seven disks in the same order, but on a different post. This is not trivial because of two restrictions. First, the only permitted action is removing the top disk from a post and dropping it onto another post. Second, a larger disk can never lie above a smaller disk on any post. (These rules imply, for example, that it is not fair to pick up the whole stack of disks at once and then to drop them all on another post!)

[height=1.5in]figures/hanoi

Figure 1: This is the starting position in the Towers of Hanoi problem. All seven disks are stacked on the leftmost post. The goal is to move all the disks to a different post. At each step the top disk on a post can be removed and dropped onto another post. At no time, however, can a larger disk lie above a smaller disk.

It is not immediately clear that a solution to this problem exists; maybe the rules are so stringent that the disks cannot all be moved to another post!

One approach to this problem is to consider a simpler variant with only three disks. We can quickly exhaust the possibilities of this simpler puzzle and find a 7-move solution like the one shown below. (The disks on each post are indicated by the numbers immediately to the right. Larger numbers correspond to larger disks. )

1 2 3  ⇒  2 3  1  ⇒  3  1  2

⇒  1 3  2 ⇒  1 3  2

⇒  1  3  2 ⇒  2 1  3

⇒  1 2 3

This problem was invented in 1883 by the French mathematician Edouard Lucas. In his original account, there were 64 disks of solid gold. At the beginning of time, all 64 were placed on a single post, and monks were assigned the task of moving them to another post according to the rules described above. According to legend, when the monks complete their task, the Tower will crumble and the world will end!

The questions we must answer are, “Given sufficient time, can the monks succeed?” and if so, “How long until the world ends?” and, most importantly, “Will this happen before the 6. 042 final?”

1.1 Finding a Recurrence

The Towers of Hanoi problem can be solved in a recurrent fashion as follows. Let T_{n} be the minimum number of steps needed to move an n-disk tower. For example, it is not hard to see that T_{1} = 1 and T_{2} = 3. For 3 disks, the solution given above shows that T_{3} ≤ 7. We can generalize the approach used for 3 disks to the following recursive algorithm for n disks.

Step 1. Move the top n − 1 disks from the first post to the third post. This can be done recursively in T_{n−1} steps.

Step 2. Move the largest disk from the first post to the to the second post. This requires just 1 step.

Step 3. Move the n − 1 disks from the third post onto the second post. Again, T_{n−1} steps are required.

This algorithm shows that T_{n}, the number of steps required for n disks, is at most T_{n} ≤ 2T_{n−1} + 1. We can now compute upper bounds on the number of steps required for various numbers of disks.

T_{3} ≤ 2 · T_{2} + 1
= 7
T_{4} ≤ 2 · T_{3} + 1
≤ 15

The algorithm answers our first question; given sufficient time, the monks can finish their task and end the world.

1.2 A Lower Bound

We can not yet compute the exact number of steps that the monks need to move the 64 disks; we can only show an upper bound. Perhaps— having pondered the problem since the beginning of time— the monks have devised a better algorithm.

In fact, there is no better algorithm, and here is why. At some step, we must move the n-th disk from the first post to a different post. For this to happen, the n−1 smaller disks must all be stacked out of the way on the only remaining post. Arranging the n − 1 smaller disks this way requires at least T_{n−1} moves. After the largest disk is moved, at least another T_{n−1} moves are required to pile the n − 1 smaller disks on top.

This argument shows that the number of steps required is at least 2T_{n−1} + 1. Since we gave an algorithm using exactly this number of steps, we now have a recurrence for T_{n}, the number of moves required to complete the Tower of Hanoi problem with n disks:

T_{n} = 2T_{n−1} + 1

Knowing the T_{1} = 1, we can use this recurrence to conclude that T_{2} = 3, T_{3} = 7, T_{4} = 15, . . ..

1.3 Guess and Verify

Computing T_{64} from the recurrence would require a lot of work. It would be nice to have a closed form expression for T_{n}, so that we could quickly compute the number of steps required to solve the Towers of Hanoi problem for any given number of disks.

(For example, we might want to know how much faster moving the disks would be if the monks donate one of the golden disks to their favorite political party as “soft money”. )

There are several different methods for solving recurrences. The simplest method is to guess the solution and then to verify that the guess is correct, usually with an induction proof. This method is called “Guess and Verify” or “substitution”. To help us make an intelligent guess, we can tabulate T_{n} for small values of n:

\begin{matrix}n & T_{n} \\ 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 15 \\ 5 & 31 \end{matrix}

From the table, a natural guess is that T_{n} = 2^{n} − 1. Whenever you guess a solution to a recurrence, you should always verify it with a proof by induction or by some other technique; after all, your guess might be wrong. (But why bother to verify in this case? After all, if we’re wrong, its not the end of the. . . no, let’s check. )

T_{n} = 2^{n} − 1

Verification. The proof is by induction on n. Let P (n) be the predicate that T_{n} = 2^{n} − 1. In the base case, P (1) is true because T_{1} = 1 = 2^{1} − 1. In the inductive step, assume T_{n} = 2^{n} − 1 to prove that T_{n+1} = 2^{n+1} − 1.

T_{n+1} = 2T_{n} + 1
= 2(2^{n} − 1) + 1
= 2^{n+1} − 1

The first equality holds by assumption, and the second follows by application of the induction hypothesis. The final step is just a simplification.

Our guess is now verified. This shows, for example, that the 7-disk puzzle will require 2^{7} − 1 = 127 moves to complete. We can also now resolve our remaining questions about the 64-disk puzzle. Since T_{64} = 2^{64} − 1, the monks must complete more than 18 billion billion steps before the world ends. Better study for the final.

1.4 The Plug and Chug Method

In general, Guess and Verify is the best way to solve a recurrence. The only problem with the method is guessing the right solution. In the Towers of Hanoi example, guessing the solution was easy, but sometimes the solution has a very strange form that is quite hard to guess. Practice helps, of course, but so can some other methods.

Plug and Chug is one such alternative method for solving recurrences. Plug and Chug is also sometimes called “expansion”, “iteration”, or “brute force”. The method consists of four calculation-intensive steps. These steps are listed for reference, but will only make real sense after we work through the Towers of Hanoi example below.

1. Expand the recurrence equation by alternately “plugging” (applying the recurrence equation) and “chugging” (simplifying the resulting expression).

2. Identify a pattern for the recurrence equation after i rounds of plug and chug. Verify that this pattern is correct by carrying out one additional round of plug and chug.

3. Substitute a value of i into the pattern so that T_{n} is expressed as a function of just the first few terms (e. g. T_{1}, T_{2}, …). Substitute computed values for these terms to obtain an ordinary, non-recurrent expression for T_{n}.

4. Find a closed form for T_{n} from the ordinary expression.

The Plug and Chug calculations for the Towers of Hanoi recurrence are worked out below.

Step 1: Plug and Chug

T_{n} = 1 + 2T_{n−1}
(plug) = 1 + 2(1 + 2T_{n−2})
(chug) = 1 + 2 + 4T_{n−2})
(plug) = 1 + 2 + 4(1 + 2T_{n−3})
(chug) = 1 + 2 + 4 + 8T_{n−3}
(plug) = 1 + 2 + 4 + 8(1 + 2T_{n−4})
(chug) = 1 + 2 + 4 + 8 + 16T_{n−4}

The first equation is the recurrence that we want to solve. In the second step, we transform the original recurrence by plugging; that is, we apply the recurrence equation to make T_{n} depend on earlier terms. In this case, we eliminate T_{n−1} and make T_{n} depend on T_{n−2} instead. Next, we chug; that is, we simplify the new expression for T_{n}. Then we plug again so that T_{n} depends on a still earlier term, T_{n−3}. Then we chug and plug and chug some more.

Step 2: Identify and Verify a Pattern

T_{n} = 1 + 2 + 4 + … + 2^{i−1} + 2^{i}T (n − i)
(plug) = 1 + 2 + 4 + … + 2^{i−1} + 2^{i}(1 + 2T_{n−(i+1)})
(chug) = 1 + 2 + 4 + … + 2^{i−1} + 2^{i} + 2^{i+1}T_{n−(i+1)})

After enough work, a pattern becomes clear: T_{n} is always a sum of consecutive powers of two together with an earlier T term.

The next step is to describe this pattern by writing down the expression obtained after i rounds of plug and chug. Then we do one last round to confirm that the pattern is correct. This check is very similar to the inductive step in a proof by induction.

Be careful in the “chug” stage; too much simplification can obscure an emerging pattern. For example, summing 1 + 2 + 4 + … at every stage would have concealed the geometric series. The rule to remember— indeed, a rule applicable to the whole of college life— is chug in moderation.

Step 3: Express n-th Term Using Early Terms

T_{n} = 1 + 2 + 4 + … + 2^{i−1} + 2^{i}T (n − i)
T_{n} = 1 + 2 + 4 + … + 2^{n−2} + 2^{n−1}T (1)
= 1 + 2 + 4 + … + 2^{n−2} + 2^{n−1}

Now we can use the pattern to express T_{n} as a function of small, computable terms. In particular, if we set i = n−1 in the above pattern, then T_{n} becomes a function only of T_{1}, which we know is equal to 1. This leaves an ordinary, non-recurrent expression for T_{n}.

Step 4: Find a Closed Form for the n-th Term

All that remains is to reduce the ordinary expression for T_{n} to a closed form. We are fortunate in this case, because T_{n} is the sum of a geometric series. We learned how to tackle these last week!

T_{n} = 1 + 2 + 4 + 8 + … + 2^{n−2} + 2^{n−1}
= ∑_{i=0}^{n−1} 2^{i}
= 2^{n} − 1

We are done! When using the Plug and Chug method, be sure to go back and verify that the answer is correct. It is very easy to make a mistake when observing the general pattern.

2 Graduate Student Job Prospects

In a certain new academic field (say computer science), there are only so many faculty positions available in all the universities of the world. Initially, there were not enough qualified candidates, and many positions were unfilled. But, over time, new graduates are filling the positions, making job prospects for later computer science students ever more bleak. Worse, the increasing number of professors are able to train an increasing number of graduate students, causing positions to fill ever more rapidly. Eventually, the universities will be saturated; new computer science graduates will have no chance at an academic career. Our problem is to determine when the universities will stop hiring new computer science faculty and, in particular, to answer the question, “Are the 6. 042 TAs doomed?” Here are the details of the problem.

• There are a total of N faculty positions available worldwide.

This number never changes due to budgetary constraints.

• Congress has passed a law forbidding forced retirement, and no one will retire voluntarily. (This is true and a problem!) In our analysis, therefore, once a faculty position is filled, it never opens up again.

• Each year, every professor trains exactly 1 student who will go on to become a professor the following year. The only exception is that first year professors do not train students; they are too busy publishing, teaching, getting grants, and serving on committees.

• In year 0, there are no computer science professors in the world.

In year 1, the first professor is hired.

2.1 Finding a Recurrence

Ideally, we could find a formula for the number of professors in the world in a given year. Then we could determine the year in which all N faculty positions are filled. Let f(n) be the number of professors during year n. To develop some intuition about the problem, we can compute values of this function for small n by hand.

f(0) = 0  No CS professors; the dark ages.
f(1) = 1  1 new professor; too busy to train a student.
f(2) = 1  1 old professor; now training a student.
f(3) = 2  1 new prof, 1 old prof; new prof too busy, old prof training.
f(4) = 3  1 new prof, 2 old profs; new prof too busy, both old profs training
f(5) = 5  2 new profs, 3 old profs
f(6) = 8  3 new profs, 5 old profs

In general, the number of professors in year n is equal to the number of professors last year plus the number of new hires. The number of professors last year is f(n − 1). The number of new hires is equal to the number of professors two years ago, f(n − 2), since each of these professors trained a student last year. These observations give the following recurrence equation for the number of professors:

f(n) = f(n − 1) + f(n − 2)  (n ≥ 2)

This is the familiar Fibonacci recurrence. Looking back, the values of f(n) that we computed by hand are indeed the first few Fibonacci numbers. Fibonacci numbers arise in all sorts of applications. So how big is f(n) anyway? Of course, we could compute as many Fibonacci numbers as we like using the recurrence, but it would be much nicer to find a closed form.

Note: When Fibonacci introduced this recurrence, the academic environment was a little bit different. So he used rabbits instead. A pair of rabbits takes one year to mature, then starts producing one pair of rabbits as offspring forever.

2.2 Solving the Recurrence

Solving the Fibonacci recurrence is easy because the recurrence is linear. (Well, “easy” in the sense that you can learn the technique in one lecture; discovering it actually took six centuries. )

Definition A recurrence is linear if it is of the form

f(n) = a_{1}f(n − 1) + a_{2}f(n − 2) + … + a_{d}f(n − d)
= ∑_{i=1}^{d} a_{i}f(n − i)

where a_{1}, a_{2}, … a_{d} are constants. The order of the recurrence is d.

For example, the Fibonacci recurrence is order 2 and has a_{1} = a_{2} = 1.

For now, let’s try to solve just the Fibonacci recurrence; we’ll see how to solve general linear recurrences later in the lecture. Our rule of thumb is that Guess and Verify is the first method to apply to a recurrence. It turns out that for a linear recurrence, an exponential solution is a good guess. However, since we know nothing beyond this, our initial Guess and Verify attempt will really only be a “dry run”; that is, we will not make an exact guess and will not verify it with a complete proof. Rather, the goal of this first attempt is only to clarify the form of the solution.

f(n) = cα^{n}

Here c and α are parameters introduced to improve our odds of having a correct guess; in the verification step, we can pick values that make the proof work. To further improve our odds, for now let’s neglect the boundary conditions, f(0) = 0 and f(1) = 1.

Verification. (dry run) Plugging our guess into the recurrence f(n) = f(n − 1) + f(n − 2) gives:

cα^{n} = cα^{n−1} + cα^{n−2}
α^{2} = α + 1
α^{2} − α − 1 = 0
α = \frac{1 ± \sqrt{5}}{2}

In the first step, both sides of the equation are divided by cα^{n−2}. The second step only involves rearranging terms. In the final step, we can compute α by solving the quadratic equation.

This calculation suggests that c can be anything, but that α must be (1 ± \sqrt{5})/2. Evidently, there are two solutions to the recurrence:

f(n) = c (\frac{1 + \sqrt{5}}{2})^{n}  or  f(n) = c (\frac{1 − \sqrt{5}}{2})^{n}

There are actually more solutions than suggested by our “dry run” of Guess and Verify; in fact, any linear combination of the above two solutions is also a solution. The following theorem states that this is true in general for linear recurrences.

Theorem 2.1 If f(n) = α_{1}^{n} and f(n) = α_{2}^{n} are two solutions to a linear recurrence (without boundary conditions), then f(n) = c_{1}a_{1}^{n} + c_{2}a_{2}^{n} is also a solution for all constants c_{1} and c_{2}.

Proof. Every linear recurrence has the following form:

f(n) = ∑_{i=1}^{d} a_{i}f(n − i)

We must prove that f(n) = c_{1}α_{1}^{n} + c_{2}α_{2}^{n} is a solution; that is, we must prove:

c_{1}α_{1}^{n} + c_{2}α_{2}^{n} = ∑_{i=1}^{d} a_{i}(c_{1}α_{1}^{n−i} + c_{2}α_{2}^{n−i})

Substituting the two solutions f(n) = α_{1}^{n} and f(n) = α_{2}^{n} into the recurrence gives the following two equations:

α_{1}^{n} = ∑_{i=1}^{d} a_{i}α_{1}^{n−i}

α_{2}^{n} = ∑_{i=1}^{d} a_{i}α_{2}^{n−i}

Multiplying the first equation by c_{1}, multiplying the second equation by c_{2}, and adding the two gives the desired result.

The theorem implies that for all c_{1} and c_{2}, the following is a solution to the Fibonacci recurrence without boundary conditions:

f(n) = c_{1} (\frac{1 + \sqrt{5}}{2})^{n} + c_{2} (\frac{1 − \sqrt{5}}{2})^{n}

All that remains is to find a solution that satisfies the boundary conditions f(0) = 0 and f(1) = 1. The first boundary condition requires that:

f(0) = c_{1} (\frac{1 + \sqrt{5}}{2})^{0} + c_{2} (\frac{1 − \sqrt{5}}{2})^{0} = 0

⇒ c_{1} + c_{2} = 0

Similarly, the second boundary condition requires that:

f(1) = c_{1} (\frac{1 + \sqrt{5}}{2})^{1} + c_{2} (\frac{1 − \sqrt{5}}{2})^{1} = 1

⇒ c_{1} (\frac{1 + \sqrt{5}}{2}) + c_{2} (\frac{1 − \sqrt{5}}{2}) = 1

We now have two linear equations in two unknowns! The system of equations is not degenerate, so there is a unique solution: c_{1} = 1/\sqrt{5} and c_{2} = −1/\sqrt{5}. We now have a complete solution to the Fibonacci recurrence with boundary conditions:

f(n) = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n}

This looks completely wrong! All Fibonacci numbers are integers, but this expression is full of square roots of five! Amazingly, however, the square roots always cancel out. This expression really does give the Fibonacci numbers if we plug in n = 0, 1, 2, . . .. If one were required to guess the solution to the Fibonacci recurrence, then it is easy to imagine taking at least six centuries to come up with this!

2.3 Job Prospects

Let’s return to the original question: how long until all N faculty positions are taken?

To answer this question, we must find the smallest n such that f(n) ≥ N. This will imply that in year n, there are as many professors as university positions. Therefore, graduates after year n will have to find other employment, e. g. shuffling golden disks in an obscure monastic community for the next 10^{19} years.

Because f(n) has such a complicated form, it is hard to compute the right value of n exactly. However, we can make a good approximation. Notice that f(n) is the sum of two terms. The key observation is that the second term tends to zero as n grows large, since |\frac{1−\sqrt{5}}{2}| = 0.618 … < 1. This means that we can rewrite f(n) with asymptotic notation as follows:

f(n) = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} + o(1)

Using this approximation for f(n), we can determine the approximate year in which all faculty positions will be taken as follows:

f(n) ≥ N
⇔ \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} + o(1) ≥ N

⇔ n ≥ \frac{log(\sqrt{5} N + o(1))}{log(\frac{1+\sqrt{5}}{2})}

This implies that all the faculty jobs will be filled in Θ(log N) years. This makes sense, since the number of professors is increasing exponentially. For example, if there are N = 10000 jobs, then all will be taken in n = 20.8 years. Now, as to the fate of the TAs, there are fewer than ten thousand faculty jobs in computer science and hiring started about 20 years ago. . .

The solution to the Fibonacci recurrence has an interesting corollary: for large n, \frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n} is very close to an integer— namely, the n-th Fibonacci number. This expression is the first term in the closed form for the n-th Fibonacci number. Since the other term of the closed form goes to zero exponentially fast and Fibonacci numbers are always integers, the first term must be very close to an integer! This is one of many strange facts about the “Golden Ratio”, \frac{1+\sqrt{5}}{2} = 1.61803 . . ..

3 General Linear Recurrences

The method we used to solve the Fibonacci recurrence can be used to solve any linear recurrence! Recall that every linear recurrence has the following form:

f(n) = ∑_{i=1}^{d} a_{i}f(n − i)

Substituting the guess f(n) = α^{n} into the recurrence gives:

α^{n} = a_{1}α^{n−1} + a_{2}α^{n−2} + … + a_{d}α^{n−d}
α^{d} = a_{1}α^{d−1} + a_{2}α^{d−2} + … + a_{d−1}α + a_{d}
α^{d} − a_{1}α^{d−1} − a_{2}α^{d−2} − … − a_{d−1}α − a_{d} = 0

The equation is divided by α^{n−d} in the first step, and terms are rearranged in the second step. The last equation is called the characteristic equation of the recurrence. The characteristic equation of a recurrence can be read of very quickly; the coefficients of the equation are the same as the coefficients of the recurrence. In general, the characteristic equation will have d roots, where d is the order of the recurrence. The solution to the recurrence depends on whether all roots of the characteristic equation are distinct.

3.1 Simple Case: Distinct Roots

If the characteristic equation has d distinct roots r_{1}, r_{2}, …, r_{d}, then the solution to the recurrence has the form:

f(n) = c_{1}r_{1}^{n} + c_{2}r_{2}^{n} + … + c_{d}r_{d}^{n}

Note that the roots of the characteristic equation need not even be real! In the end, imaginary parts will cancel just as the \sqrt{5}’s canceled in the solution to the Fibonacci recurrence.

The constants c_{1}, c_{2}, …, c_{d} depend on the boundary conditions. Each boundary condition generates a linear equation in these constants. For example, the boundary conditions f(0) = b_{0}, f(1) = b_{1}, …, f(d−1) = b_{d−1} generate the linear equations:

b_{0} = c_{1} + c_{2} + … + c_{d}
b_{1} = c_{1}r_{1} + c_{2}r_{2} + … + c_{d}r_{d}
. . . . . . . . .
b_{d−1} = c_{1}r_{1}^{d−1} + c_{2}r_{2}^{d−1} + … + c_{d}r_{d}^{d−1}

If there are d boundary conditions, then we obtain d linear equations in d unknowns. A neat linear algebra fact is that a system of equations of this particular type is never degenerate. This means that for every set of constants b_{0}, b_{1}, … b_{d−1} in the boundary conditions, we can find a unique set of constants c_{0}, c_{1}, … c_{d−1} that give a solution to the recurrence and satisfy the boundary conditions.

3.2 Tricky Case: Repeated Roots

If the characteristic equation of a recurrence has a repeated root, then the solution is slightly more complicated. The main tool is the following theorem, which we will not prove.

Theorem 3.1 If r is a root of the characteristic equation of a recurrence with multiplicity m, then all of r^{n}, nr^{n}, n^{2}r^{n}, … n^{m−1}r^{n} are solutions to the recurrence.

For example, if the characteristic equation of a recurrence has root r_{1} with multiplicity 2, root r_{2} with multiplicity 1, and root r_{3} with multiplicity 3, then the solution to the recurrence has the form:

f(n) = c_{1}r_{1}^{n} + c_{2}nr_{1}^{n} + c_{3}r_{2}^{n} + c_{4}r_{3}^{n} + c_{5}nr_{3}^{n} + c_{6}n^{2}r_{3}^{n}

As before, the constants depend on the boundary conditions. Each boundary condition generates a linear equation, and the constants are computed by solving the resulting system of linear equations. In this respect, solving linear recurrences is very similar to solving linear differential equations.

3.3 An Example of the Tricky Case

To understand recurrences of this tricky type, let’s work an example.

Suppose that there is a type of plant that lives forever, but only reproduces during the first year of life. How fast will the plant population grow? (Notice that this is just the reverse of the graduate student job problem where faculty “reproduce” in every year except the first. )

Let f(n) be the number of plants in year n. As boundary conditions, define f(0) = 0 and f(1) = 1. The plant population in year n is equal to the population from the year before plus the number of new plants. The population from the year before is f(n − 1). The number of new plants this year is equal to the number of new plants last year or f(n − 1) − f(n − 2). We can now form a recurrence equation for the plant population:

f(n) = f(n − 1) + (f(n − 1) − f(n − 2))
= 2f(n − 1) − f(n − 2)
f(n) − 2f(n − 1) + f(n − 2) = 0

The characteristic equation is α^{2} − 2α + 1 = 0, which has the single root α = 1 with multiplicity 2. Therefore, the solution to the recurrence has the form:

f(n) = c_{1}(1)^{n} + c_{2}n(1)^{n}
= c_{1} + c_{2}n

The boundary conditions, f(0) = 0 and f(1) = 1, generate the following linear equations:

0 = c_{1} + c_{2}(0)
1 = c_{1} + c_{2}(1)

The solution to the linear system is c_{1} = 0 and c_{2} = 1. Therefore, the solution to the recurrence is:

f(n) = c_{1} + c_{2}n
= 0 + (1)n
= n

The answer turns out to be very simple! In year n, there are exactly n plants. Of course, we probably could have solved this problem more easily with Guess and Verify, but for many other examples, guessing is not so easy.

4 Inhomogeneous Recurrences

We can now solve all recurrences of the form:

f(n) − a_{1}f(n − 1) − … − a_{d}f(n − d) = 0

Strictly speaking, this is the family of linear homogeneous recurrences. These recurrences are called homogeneous because the right side of the equation is 0. If the right side were 1 or n^{2} or some arbitrary function g(n), then the recurrence would be called inhomogeneous.

Definition An inhomogeneous linear recurrence has the form:

f(n) − a_{1}f(n − 1) − a_{2}f(n − 2) − … − a_{d}f(n − d) = g(n)

where a_{1}, a_{2}, … a_{d} are constants.

Inhomogeneous recurrences are trickier than homogeneous ones. Remember that we used the following fact: if two distinct functions satisfy a linear recurrence, then their sum does too.

This is no longer true for inhomogeneous recurrences: if we have two functions f_{1} and f_{2} that satisfy the inhomogeneous recurrence, that is to say,

f_{1}(n) − ∑_{i=1}^{d} a_{i}f_{1}(n − d) = g(n)

f_{2}(n) − ∑_{i=1}^{d} a_{i}f_{2}(n − d) = g(n)

then their sum s(n) = f_{1}(n) + f_{2}(n) satisfies

s(n) − ∑_{i=1}^{d} a_{i}s(n − d) = 2g(n)

(we can see this by adding the equations for f_{1} and f_{2}. However, if we substract the equations for f_{1} and f_{2}, and define t(n) = f_{1}(n) − f_{2}(n), then we find that

t(n) − ∑_{i=1}^{d} a_{i}t(n − d) = 0,

that is, the difference t(n) satisfies the homogeneous portion of the inhomogeneous equation. This leads to an approach for inhomogeneous linear recurrences: solve the inhomogeneous part once, and then add in the homogeneous part to deal with the boundary conditions.

There are three steps to solving an inhomogeneous linear recurrence.

1. Replace g(n) by 0 and solve the resulting homogeneous recurrence.

(Ignore boundary conditions for now; that is, do not solve for constants c_{1}, c_{2}, …, c_{d}. ) The solution to the homogeneous recurrence is called the homogeneous solution.

2. Restore g(n) and find a single solution to the recurrence, again ignoring boundary conditions. This is called the particular solution. (This is the hard part!)

3. Add the homogeneous and particular solutions together to obtain the general solution. Now use the boundary conditions to determine the constant factors by the usual method of generating and solving a system of linear equations.

Notice that the method for solving inhomogeneous linear recurrences is closely analogous to the method for solving inhomogeneous linear differential equations!

4.1 An Example of an Inhomogeneous Recurrence

Let f(n) = 4f(n − 1) + 3^{n} and, as a boundary condition, let f(1) = 1. This is an inhomogeneous linear recurrence.

Step 1: Solve the Homogeneous Recurrence

The homogeneous recurrence is f(n) − 4f(n − 1) = 0. The characteristic equation is α − 4 = 0. The only root is α = 4. Therefore, the homogeneous solution is c_{1}4^{n}.

Step 2: Find a Particular Solution

We must find a single solution to the recurrence f(n) = 4f(n − 1) + 3^{n}. This is usually the hard part of solving an inhomogeneous linear recurrence. Let’s guess that there is a solution of the form c3^{n}. Substituting this into the recurrence gives:

f(n) = 4f(n − 1) + 3^{n}
c3^{n} = 4c3^{n−1} + 3^{n}
3c = 4c + 3
c = −3

The equation was divided by 3^{n−1} in the first step. The second and third steps were only simplification. We now have a particular solution, f(n) = −3 · 3^{n} = −3^{n+1}.

Step 3: Add Solutions and Find Constants

We now add the homogeneous solution and the particular solution to obtain the general solution:

f(n) = c_{1}4^{n} − 3^{n+1}

The value of the constant is obtained from the boundary condition, f(1) = 1:

1 = c_{1}4^{1} − 3^{1+1}
= 4c_{1} − 9
c_{1} = 5/2

The solution to the recurrence is f(n) = \frac{5}{2}4^{n} − 3^{n+1}!

Since we could easily have made a mistake, let’s check to make sure that our solution at least works for n = 2. From the recurrence, f(2) = 4f(1) + 3^{2} = 13. From our closed form, f(2) = \frac{5}{2}4^{2} − 3^{3} = 40 − 27 = 13. It looks right!

4.2 Hanoi

Now we can sledgehammer the Hanoi problem. Recall the recurrence:

T (n) = 2T (n − 1) + 1.

Let’s apply our approach:

Step 1: Solve the Homogeneous Recurrence

The homogeneous recurrence is T (n) − 2T (n − 1) = 0. The characteristic equation is α − 2 = 0. The only root is α = 2. Therefore, the homogeneous solution is c2^{n}.

Step 2: Find a Particular Solution

Now we need a single solution to the recurrence T (n) = 2T (n−1)+1 Let’s guess a constant solution b. Is there a solution to b = 2b + 1? Yes! Namely, b = −1. So this is particular solution.

Step 3: Add Solutions and Find Constants

Adding the homogeneous solution and the particular solution gives the general solution:

T (n) = c2^{n} − 1

Plugging in the boundary conditions gives 0 = T (0) = c − 1 which tells us that c = 1. So we get the expected answer T (n) = 2^{n} − 1.

4.3 A Final Example

Let f(n) = 4f(n − 1) − 4f(n − 2) + n and, as a boundary condition, let f(0) = 4 and f(1) = 7.

Step 1: Solve the Homogeneous Recurrence

The homogeneous recurrence is f(n) − 4f(n − 1) + 4f(n − 2) = 0. The characteristic equation is α^{2} − 4α + 4. The only root is α = 2 with multiplicity 2. Therefore, the homogeneous solution is c_{1}2^{n} + c_{2}n2^{n}.

Step 2: Find a Particular Solution

Now we need a single solution to the recurrence f(n) = 4f(n − 1) − 4f(n − 2) + n. Let’s guess a solution of the form an + b and substitute into the recurrence:

f(n) = 4f(n − 1) − 4f(n − 2) + n
an + b = 4(a(n − 1) + b) − 4(a(n − 2) + b) + n
= 4an − 4a + 4b − 4an + 8a − 4b + n
= 4a + n
⇒ a = 1, b = 4a = 4

This gives the particular solution f(n) = n + 4.

Step 3: Add Solutions and Find Constants

Adding the homogeneous solution and the particular solution gives the general solution:

f(n) = c_{1}2^{n} + c_{2}n2^{n} + n + 4

The values of the constants are obtained from the boundary conditions, f(0) = 4 and f(1) = 7.

4 = c_{1}2^{0} + 0c_{2}2^{0} + 0 + 4
= c_{1} + 4
c_{1} = 0
7 = c_{1}2^{1} + 1c_{2}2^{1} + 1 + 4
= 2c_{1} + 2c_{2} + 5
c_{2} = 1

The solution to the recurrence is f(n) = n2^{n} + n + 4.

4.4 Finding a Particular Solution

The hardest part in solving inhomogeneous recurrences is finding a particular solution. There are some good rules of thumb, however. Suppose the recurrence has the form:

f(n) − a_{1}f(n − 1) − a_{2}f(n − 2) − … − a_{d}f(n − d) = g(n)

If g(n) is a polynomial of degree r, then guess that f(n) is a polynomial of degree r. For example, if g(n) = n^{2}, then guess f(n) = an^{2} +bn+c and determine a, b, and c by substituting and verifying. If a degree r polynomial does not work, then try degree r + 1 and so on.

Similarly, if g(n) is an exponential, then guess that f(n) is an exponential. For example, if g(n) = 2^{n} + 3^{n}, then guess f(n) = a2^{n} + b3^{n}. In general, guess a particular solution with the same form as g(n).

5 Divide and Conquer Recurrences

We now turn to another family of recurrences known as Divide and Conquer recurrences. These arise in recursive algorithms that partition their inputs into smaller pieces in order to solve the problem.

5.1 The Merge Sort Algorithm

As a motivating example, we will consider Merge Sort. There are many algorithms for sorting a list of n items; in fact, you will see a dozen of them in 6. 046. Merge sort is one of the most popular.

Here is how Merge Sort works. The input is a list of n ≥ 1 items x_{1}, x_{2}, …, x_{n}. If n = 1, then the algorithm returns the single item x_{1}. If n > 1, then the original list is broken into two lists, x_{1}, …, x_{n/2} and x_{n/2+1}, …, x_{n}. Both of these lists are sorted recursively, and then they are merged to form a complete, sorted list of the original n items. All work is in the merging operation; the details are explained in the following example.

Suppose we want to sort the list 10, 7, 23, 5, 2, 4, 3, 9. Since the number of items is greater than 1, we divide into two lists; one is 10, 7, 23, 5, and the other is 2, 4, 3, 9. Each list is sorted recursively.

The results are 5, 7, 10, 23 and 2, 3, 4, 9.

Now we must merge these two small sorted lists into one big sorted list. (In this case, the “small” lists have 4 items apiece, and the “big” list will eventually have 8 items. ) We start with the big list empty and add one item at a time. At each step, we compare the first items in the small lists. We remove the smaller item and append it to the end of the big list. This process repeats until one of the small lists becomes empty. At that point, the remaining small list is appended to the big list and we are done.

For the example, the contents of the three lists after each step are shown in the table below.

small list 1 small list 2 big list
5, 7, 10, 23 2, 3, 4, 9
5, 7, 10, 23 3, 4, 9  2
5, 7, 10, 23 4, 9  2, 3
5, 7, 10, 23 9  2, 3, 4
7, 10, 23  9  2, 3, 4, 5
10, 23  9  2, 3, 4, 5, 7
10, 23  2, 3, 4, 5, 7, 9
2, 3, 4, 5, 7, 9, 10, 23

5.2 Finding a Recurrence

In the analysis of a sorting algorithm, a traditional question is, “What is the maximum number comparisons used in sorting n items?” The number of comparisons is taken as an estimate of the run time. In the case of Merge Sort, we can find a recurrence for this quantity. Solving the recurrence will allow us to study the asymptotic behavior of the algorithm.

To make the analysis easier, assume for now that the number of items we are sorting is a power of 2. This ensures that we can divide the list of items exactly in half at every stage of the recursion.

Let T (n) be the maximum number of comparisons used by Merge Sort in sorting a list of n items. If n > 1, then this is equal to the number of comparisons used in sorting both halves of the list plus the number of comparisons used in merging the two halves.

The number of comparisons used in sorting each half of the list is T (n/2). Sorting both halves requires 2T (n/2) comparisons. The number of comparisons used in merging the two halves is at most n − 1. The reason is that one item is appended to the big list after each comparison, and at least one additional item is appended to the big list in the final step when one small list becomes empty. Since the big list eventually contains n items, there can be at most n − 1 comparisons.

(Of course, there might be fewer comparisons, but we are analyzing the worst case. )

Adding all comparisons gives the following recurrence:

T (n) = 2T (n/2) + n − 1

No comparisons are required to sort a list with a single item, so T (1) = 0. From this fact and the recurrence, we can compute T (2) = 2T (1)+2−1 = 1, T (4) = 2T (2)+4−1 = 5, T (8) = 2T (3) + 8 − 1 = 17, T (16) = 2T (4) + 16 − 1 = 49, etc.

5.3 Solving the Recurrence

We would like to find a closed form for the number of comparisons used by Merge Sort in sorting a list of n items. This requires solving the recurrence T (n) = 2T (n/2) + n − 1. The first method to try is Guess and Verify. The problem is that there is no obvious pattern to the values from small cases, 0, 1, 5, 17, 49. Our only other method is Plug and Chug. Here we go:

Step 1: Plug and Chug

T (n) = n − 1 + 2T (n/2)
(plug) = n − 1 + 2(n/2 − 1 + 2T (n/4))
(chug) = n − 1 + n − 2 + 4T (n/4)
(plug) = n − 1 + n − 2 + 4(n/4 − 1 + 2T (n/8))
(chug) = n − 1 + n − 2 + n − 4 + 8T (n/8)
(plug) = n − 1 + n − 2 + n − 4 + 8(n/8 − 1 + 2T (n/16))
(chug) = n − 1 + n − 2 + n − 4 + n − 8 + 16T (n/16)

A pattern has emerged. Note that too much simplification would have obscured the pattern.

Step 2: Identify and Verify a Pattern

T (n) = n − 1 + n − 2 + … + n − 2^{i−1} + 2^{i}T (n/2^{i})
(plug) = n − 1 + n − 2 + … + n − 2^{i−1} + 2^{i}(n/2^{i} − 1 + 2T (n/2^{i+1}))
(chug) = n − 1 + n − 2 + … + n − 2^{i−1} + n − 2^{i} + 2^{i+1}T (n/2^{i+1})

The additional round of plug and chug confirms that the pattern is correct.

Step 3: Express n-th Term Using Early Terms

We must substitute a value for i into the pattern so that T (n) depends on only small terms. A natural choice is i = log_{2} n, since then T (n/2^{i}) = T (1). This substitution makes T (n) dependent only on T (1), which we know is 0.

T (n) = n − 1 + n − 2 + … + n − 2^{i−1} + 2^{i}T (n/2^{i})
= n − 1 + n − 2 + … + n − 2^{log_{2}(n)−1} + 2^{log_{2} n}T (n/2^{log_{2} n})
= n − 1 + n − 2 + … + n − 2^{log_{2}(n)−1} + 2^{log_{2} n}T (1)
= n − 1 + n − 2 + … + n − 2^{log_{2}(n)−1}

In the final equation, we used the fact that T (1) = 0; this completely eliminates the last term in the summation.

Step 4: Find a Closed-Form for the n-th Term

Now we have an ordinary, non-recurrent expression for T (n). We can reduce this to a closed form by summing a series.

T (n) = n − 1 + n − 2 + … + n − 2^{i−1} + n − 2^{log_{2}(n)−1}
= ∑_{i=0}^{log_{2}(n)−1} n − 2^{i}

= ∑_{i=0}^{log_{2}(n)−1} n − ∑_{i=0}^{log_{2}(n)−1} 2^{i}
= n log_{2} n − (2^{log_{2} n} − 1)
= n log_{2} n − n + 1
∼ n log_{2} n

What a weird answer— we never would have guessed this! To make sure that there is no error, we can check that the formula gives the same values for T (n) that we computed earlier:

n  n log_{2} n − n + 1
1  1 log_{2} 1 − 1 + 1 = 0
2  2 log_{2} 2 − 2 + 1 = 1
4  4 log_{2} 4 − 4 + 1 = 5
8 8 log_{2} 8 − 8 + 1 = 17
16 16 log_{2} 16 − 16 + 1 = 49

Sure enough! Note that the n log_{2} n comparisons used by Merge Sort are far fewer than the total of n(n − 1)/2 possible comparisons.

6 More Recurrences

Let’s compare the Tower of Hanoi and Merge Sort recurrences.

T (n) = 2T (n − 1) + 1  T (n) ∼ 2^{n}
T (n) = 2T (n/2) + n − 1  T (n) ∼ n log_{2} n

In the Towers of Hanoi, we divided a problem of size n into two subproblems of size n − 1 and did only 1 additional step (moving the largest disk). In Merge Sort, we divided a problem of size n into two subproblems of size just n/2, but we did as many as n − 1 additional steps (merging two sublists). Which algorithm runs faster? Merge Sort by a mile! The key point is that generating smaller subproblems is far more important than reducing the additional steps per recursive call.

Let’s vary the above recurrences slightly and see how the solutions change.

6.1 A Speedy Algorithm

Suppose we have a speedy algorithm with the best properties of both earlier algorithms; that is, at each stage the problem is divided in half and we do only one additional step. The run time is described by the following recurrence:

S(1) = 0
S(n) = 2S(n/2) + 1

(Another interpretation of this recurrence is that S(n) is the number recursive calls made when Merge Sort is run on a list of n items. )

Guess and Verify is the first method to try. (Plug and Chug also works. ) To motivate a guess, let’s tabulate a few values of S(n). As before, assume that n is a power of two.

\begin{matrix}n & S(n) \\ 1 & 0 \\ 2 & 2S(1) + 1 = 1 \\ 4 & 2S(2) + 1 = 3 \\ 8 & 2S(4) + 1 = 7 \end{matrix}

S(n) = n − 1 Verification. The proof is by strong induction on n. Let P (n) be the predicate that if n is a power of two, then S(n) = n − 1. In the base case, P (1) is true because S(1) = 0 by assumption. In the inductive step, for n ≥ 2 assume P (1), P (2), …, and P (n − 1) to prove P (n). If n is not a power of two, then P (n) is vacuously true. Otherwise, we have:

S(n) = 2S(n/2) + 1
= 2(n/2 − 1) + 1
= n − 1

The first equation is the recurrence. The second equality follows from the induction hypothesis, and the last step is simplification only.

The run time of this speedy algorithm is ∼ n. This is better than the ∼ n log n run time of Merge Sort, but only slightly so. This is consistent with the idea that decreasing the number of additional steps per recursive call is much less important than reducing the size of subproblems.

6.2 A Verification Problem

Sometimes verifying the solution to a recurrence using induction can be tricky. For example, suppose that we have the same recurrence as before, but we only try to prove that S(n) ≤ n. This is true, but the proof goes awry!

S(n) ≤ n

Verification (attempt). The proof is by strong induction. Let P (n) be the predicate that if n is a power of two, then S(n) ≤ n. In the base case, P (1) is true because S(1) = 0 ≤ 1. In the inductive step, for n ≥ 2, assume P (1), P (2), …, P (n − 1) to prove P (n). If n is not a power of two, then P (n) is vacuously true. Otherwise, we have:

S(n) = 2S(n/2) + 1
≤ 2(n/2) + 1
= n + 1
≰ n

The first equation is the recurrence. The second equality follows by induction.

The third step is a simplification, and in the fourth step we crash and burn spectacularly.

We know that the result is true, but the proof did not work! The natural temptation is to ease up and try to prove something weaker, say S(n) ≤ n + 1 or even S(n) ≤ 2n. Bad plan!

As was often the case with other induction proofs, the trick is to choose a stronger induction hypothesis! In particular, if we use the stronger hypothesis that S(n) ≤ n − 1, then the proof goes through. The crux of the argument in the inductive step is shown below.

S(n) = 2S(n/2) + 1
≤ 2(n/2 − 1) + 1
= n − 1
≤ n − 1

As before, the first equation is the recurrence, the second follows by induction, and the third is a simplification. The final inequality shows that the induction hypothesis holds for P (n) as desired.

6.3 A False Proof

What happens if we try an even stronger induction hypothesis? Shouldn’t the proof work out even more easily? For example, suppose our hypothesis is that S(n) ≤ n − 2. This hypothesis is false, since we proved that S(n) = n − 1. But let’s see where the proof breaks. Here again is the crux of the argument:

S(n) = 2S(n/2) + 1
≤ 2(n/2 − 2) + 1
= n − 3
≤ n − 2

Something is wrong; we proved a false statement! The problem is that we were lazy and did not writ