Recurrent Problems

three sample problems that give a feel for
what’s to come. They have two traits in common: They’ve all been investigated
repeatedly by mathematicians; and their solutions all use the idea of
recuvexe, in which the solution to each problem depends on the solutions
to smaller instances of the same problem.
Raise your hand
if you’ve never
seen this.
OK, the rest of
you can cut to
equation (1.1).
1.1 THE TOWER OF HANOI
Let’s look first at a neat little puzzle called the Tower of Hanoi,
invented by the French mathematician Edouard Lucas in 1883. We are given
a tower of eight disks, initially stacked in decreasing size on one of three pegs:
The objective is to transfer the entire tower to one of the other pegs, moving
only one disk at a time and never moving a larger one onto a smaller.
Lucas [208] furnished his toy with a romantic legend about a much larger
Gold -wow. Tower of Brahma, which supposedly has 64 disks of pure gold resting on three
Are our disks made
of concrete?
diamond needles. At the beginning of time, he said, God placed these golden
disks on the first needle and ordained that a group of priests should transfer
them to the third, according to the rules above. The priests reportedly work
day and night at their task. When they finish, the Tower will crumble and
the world will end.
1
2 RECURRENT PROBLEMS
It’s not immediately obvious that the puzzle has a solution, but a little
thought (or having seen the problem before) convinces us that it does. Now
the question arises: What’s the best we can do? That is, how many moves
are necessary and sufficient to perform the task?
The best way to tackle a question like this is to generalize it a bit. The
Tower of Brahma has 64 disks and the Tower of Hanoi has 8; let’s consider
what happens if there are n disks.
One advantage of this generalization is that we can scale the problem
down even more. In fact, we’ll see repeatedly in this book that it’s advantageous
to LOOK AT SMALL CASES first. It’s easy to see how to transfer a tower
that contains only one or two disks. And a small amount of experimentation
shows how to transfer a tower of three.
The next step in solving the problem is to introduce appropriate notation:
NAME AND CONQUER. Let’s say that T,, is the minimum number of moves
that will transfer n disks from one peg to another under Lucas’s rules. Then
Tl is obviously 1, and T2 = 3.
We can also get another piece of data for free, by considering the smallest
case of all: Clearly TO = 0, because no moves at all are needed to transfer a
tower of n = 0 disks! Smart mathematicians are not ashamed to think small,
because general patterns are easier to perceive when the extreme cases are
well understood (even when they are trivial).
But now let’s change our perspective and try to think big; how can we
transfer a large tower? Experiments with three disks show that the winning
idea is to transfer the top two disks to the middle peg, then move the third,
then bring the other two onto it. This gives us a clue for transferring n disks
in general: We first transfer the n - 1 smallest to a different peg (requiring
T,-l moves), then move the largest (requiring one move), and finally transfer
the n- 1 smallest back onto the largest (requiring another Tn..1 moves). Thus
we can transfer n disks (for n > 0) in at most 2T,-, + 1 moves:
T, 6 2Tn-1 + 1 , for n > 0.
This formula uses ‘ < ’ instead of ‘ = ’ because our construction proves only
that 2T+1 + 1 moves suffice; we haven’t shown that 2T,_, + 1 moves are
necessary. A clever person might be able to think of a shortcut.
But is there a better way? Actually no. At some point we must move the
largest disk. When we do, the n - 1 smallest must be on a single peg, and it
has taken at least T,_, moves to put them there. We might move the largest
disk more than once, if we’re not too alert. But after moving the largest disk
for the last time, we must transfer the n- 1 smallest disks (which must again
be on a single peg) back onto the largest; this too requires T,- 1 moves. Hence
Most of the published
“solutions”
to Lucas’s problem,
like the early one
of Allardice and
Fraser [?I, fail to explain
why T,, must
be 3 2T,, 1+ 1.
Tn 3 2Tn-1 + 1 , for n > 0.
Yeah, yeah.
lseen that word
before.
Mathematical induction
proves that
we can climb as
high as we like on
a ladder, by proving
that we can climb
onto the bottom
rung (the basis)
and that from each
rung we can climb
up to the next one
(the induction).
1.1 THE TOWER OF HANOI 3
These two inequalities, together with the trivial solution for n = 0, yield
To =O;
T, = 2T+1 +l , for n > 0.
(1.1)
(Notice that these formulas are consistent with the known values TI = 1 and
Tz = 3. Our experience with small cases has not only helped us to discover
a general formula, it has also provided a convenient way to check that we
haven’t made a foolish error. Such checks will be especially valuable when we
get into more complicated maneuvers in later chapters.)
A set of equalities like (1.1) is called a recurrence (a.k.a. recurrence
relation or recursion relation). It gives a boundary value and an equation for
the general value in terms of earlier ones. Sometimes we refer to the general
equation alone as a recurrence, although technically it needs a boundary value
to be complete.
The recurrence allows us to compute T,, for any n we like. But nobody
really likes to compute from a recurrence, when n is large; it takes too long.
The recurrence only gives indirect, “local” information. A solution to the
recurrence would make us much happier. That is, we’d like a nice, neat,
“closed form” for T,, that lets us compute it quickly, even for large n. With
a closed form, we can understand what T,, really is.
So how do we solve a recurrence? One way is to guess the correct solution,
then to prove that our guess is correct. And our best hope for guessing
the solution is to look (again) at small cases. So we compute, successively,
T~=2~3+1=7;T~=2~7+1=15;T~=2~15+1=31;T~=2~31+1=63.
Aha! It certainly looks as if
T, = 2n-1, for n 3 0. (1.2)
At least this works for n < 6.
Mathematical induction is a general way to prove that some statement
about the integer n is true for all n 3 no. First we prove the statement
when n has its smallest value, no; this is called the basis. Then we prove the
statement for n > no, assuming that it has already been proved for all values
between no and n - 1, inclusive; this is called the induction. Such a proof
gives infinitely many results with only a finite amount of work.
Recurrences are ideally set up for mathematical induction. In our case,
for example, (1.2) follows easily from (1.1): The basis is trivial, since TO =
2’ - 1 = 0. And the induction follows for n > 0 if we assume that (1.2) holds
when n is replaced by n - 1:
T,, = 2T,, , $1 = 2(2 n l -l)+l = 2n-l.
Hence (1.2) holds for n as well. Good! Our quest for T,, has ended successfully.
4 RECURRENT PROBLEMS
Of course the priests’ task hasn’t ended; they’re still dutifully moving
disks, and will be for a while, because for n = 64 there are 264-l moves (about
18 quintillion). Even at the impossible rate of one move per microsecond, they
will need more than 5000 centuries to transfer the Tower of Brahma. Lucas’s
original puzzle is a bit more practical, It requires 28 - 1 = 255 moves, which
takes about four minutes for the quick of hand.
The Tower of Hanoi recurrence is typical of many that arise in applications
of all kinds. In finding a closed-form expression for some quantity of
interest like T,, we go through three stages:
1 Look at small cases. This gives us insight into the problem and helps us
in stages 2 and 3.
2 Find and prove a mathematical expression for the quantity of interest. What is a proof?
For the Tower of Hanoi, this is the recurrence (1.1) that allows us, given “One ha’fofone
the inclination, to compute T,, for any n.
percent pure alcohol.
”
3 Find and prove a closed form for our mathematical expression. For the
Tower of Hanoi, this is the recurrence solution (1.2).
The third stage is the one we will concentrate on throughout this book. In
fact, we’ll frequently skip stages 1 and 2 entirely, because a mathematical
expression will be given to us as a starting point. But even then, we’ll be
getting into subproblems whose solutions will take us through all three stages.
Our analysis of the Tower of Hanoi led to the correct answer, but it
required an “inductive leap”; we relied on a lucky guess about the answer.
One of the main objectives of this book is to explain how a person can solve
recurrences without being clairvoyant. For example, we’ll see that recurrence
(1.1) can be simplified by adding 1 to both sides of the equations:
To + 1 = 1;
Lsl =2T,-, +2, for n > 0.
Now if we let U, = T,, + 1, we have
uo = 1 ;
u, = 2&-l, for n > 0.
Interesting: We get
rid of the +l in
(1.1) by adding, not
(1.3) by subtracting.
It doesn’t take genius to discover that the solution to this recurrence is just
U, = 2”; hence T, = 2” - 1. Even a computer could discover this.
1.2 LINES IN THE PLANE
Our second sample problem has a more geometric flavor: How many
slices of pizza can a person obtain by making n straight cuts with a pizza
knife? Or, more academically: What is the maximum number L, of regions
1.2 LINES IN THE PLANE 5
(A pizza with Swiss
cheese?)
A region is convex
if it includes all
line segments between
any two of its
points. (That’s not
what my dictionary
says, but it’s what
mathematicians
believe.)
defined by n lines in the plane? This problem was first solved in 1826, by the
Swiss mathematician Jacob Steiner [278].
Again we start by looking at small cases, remembering to begin with the
smallest of all. The plane with no lines has one region; with one line it has
two regions; and with two lines it has four regions:
(Each line extends infinitely in both directions.)
Sure, we think, L, = 2”; of course! Adding a new line simply doubles
the number of regions. Unfortunately this is wrong. We could achieve the
doubling if the nth line would split each old region in two; certainly it can
split an old region in at most two pieces, since each old region is convex. (A
straight line can split a convex region into at most two new regions, which
will also be convex.) But when we add the third line-the thick one in the
diagram below- we soon find that it can split at most three of the old regions,
no matter how we’ve placed the first two lines:
Thus L3 = 4 + 3 = 7 is the best we can do.
And after some thought we realize the appropriate generalization. The
nth line (for n > 0) increases the number of regions by k if and only if it
splits k of the old regions, and it splits k old regions if and only if it hits the
previous lines in k- 1 different places. Two lines can intersect in at most one
point. Therefore the new line can intersect the n- 1 old lines in at most n- 1
different points, and we must have k 6 n. We have established the upper
bound
L 6 L-1 +n, for n > 0.
Furthermore it’s easy to show by induction that we can achieve equality in
this formula. We simply place the nth line in such a way that it’s not parallel
to any of the others (hence it intersects them all), and such that it doesn’t go
6 RECURRENT PROBLEMS
through any of the existing intersection points (hence it intersects them all
in different places). The recurrence is therefore
Lo = 1;
L, = L,-l +n, for n > 0. (1.4)
The known values of L1 , Lz, and L3 check perfectly here, so we’ll buy this.
Now we need a closed-form solution. We could play the guessing game
again, but 1, 2, 4, 7, 11, 16, . . . doesn’t look familiar; so let’s try another
tack. We can often understand a recurrence by “unfolding” or “unwinding”
it all the way to the end, as follows:
L, = L,_j + n
= L,-z+(n-l)+n
= LnP3 + (n - 2) + (n - 1) + n
Unfolding?
I’d call this
“plugging in.”
= Lo+1 +2+... + (n - 2) + (n - 1) + n
= 1 + s,, where S, = 1 + 2 + 3 + . . + (n - 1) + n.
In other words, L, is one more than the sum S, of the first n positive integers.
The quantity S, pops up now and again, so it’s worth making a table of
small values. Then we might recognize such numbers more easily when we
see them the next time:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14
S, 1 3 6 10 15 21 28 36 45 55 66 78 91 105
These values are also called the triangular numbers, because S, is the number
of bowling pins in an n-row triangular array. For example, the usual four-row
array ‘*:::*’ has Sq = 10 pins.
To evaluate S, we can use a trick that Gauss reportedly came up with
in 1786, when he was nine years old [73] (see also Euler [92, part 1, $4151): It seems a lot of
stuff is attributed
s,= 1 + 2 + 3 + . . . + ( n - l ) + n to Gausseither
he was really
+Sn= n + (n-l) + (n-2) + ... + 2 + 1 smart or he had a
2S, = (n+l) + (n+l) + (n+l) +...+ (n+1) + (n+l)
great press agent.
Maybe he just
We merely add S, to its reversal, so that each of the n columns on the right
sums to n + 1. Simplifying,
~~~s~n~,!~etic
s _ n(n+l)
n- 2 ’
for n 3 0. (1.5)
Actually Gauss is
often called the
greatest mathematician
of all time.
So it’s nice to be
able to understand
at least one of his
discoveries.
When in doubt,
look at the words.
Why is it Vlosed,”
as opposed to
L’open”? What
image does it bring
to mind?
Answer: The equation
is “closed ” not
defined in ter;s of
itself-not leading
to recurrence. The
case is “closed” -it
won’t happen again.
Metaphors are the
key.
Is “zig” a technical
term?
1.2 LINES IN THE PLANE 7
OK, we have our solution:
L
n
= n(n+‘) $1
2 )
for n 3 0. (1.6)
As experts, we might be satisfied with this derivation and consider it
a proof, even though we waved our hands a bit when doing the unfolding
and reflecting. But students of mathematics should be able to meet stricter
standards; so it’s a good idea to construct a rigorous proof by induction. The
key induction step is
L, = L,-lfn = (t(n-l)n+l)+n = tn(n+l)+l.
Now there can be no doubt about the,closed form (1.6).
Incidentally we’ve been talking about “closed forms” without explicitly
saying what we mean. Usually it’s pretty clear. Recurrences like (1.1)
and (1.4) are not in closed form- they express a quantity in terms of itself;
but solutions like (1.2) and (1.6) are. Sums like 1 + 2 + . . . + n are not in
closed form- they cheat by using ’ . . . ‘; but expressions like n(n + 1)/2 are.
We could give a rough definition like this: An expression for a quantity f(n)
is in closed form if we can compute it using at most a fixed number of “well
known” standard operations, independent of n. For example, 2” - 1 and
n(n + 1)/2 are closed forms because they involve only addition, subtraction,
multiplication, division, and exponentiation, in explicit ways.
The total number of simple closed forms is limited, and there are recurrences
that don’t have simple closed forms. When such recurrences turn out
to be important, because they arise repeatedly, we add new operations to our
repertoire; this can greatly extend the range of problems solvable in “simple”
closed form. For example, the product of the first n integers, n!, has proved
to be so important that we now consider it a basic operation. The formula
‘n!’ is therefore in closed form, although its equivalent ‘1 .2.. . . .n’ is not.
And now, briefly, a variation of the lines-in-the-plane problem: Suppose
that instead of straight lines we use bent lines, each containing one “zig!’
What is the maximum number Z, of regions determined by n such bent lines
in the plane? We might expect Z, to be about twice as big as L,, or maybe
three times as big. Let’s see:
<
2
1
8 RECURRENT PROBLEMS
From these small cases, and after a little thought, we realize that a bent . . and a little
line is like two straight lines except that regions merge when the “two” lines afterthought...
don’t extend past their intersection point.
. 4
’ .
.
3 .::: 1
. . . . . 2(=:
Regions 2, 3, and 4, which would be distinct with two lines, become a single
region when there’s a bent line; we lose two regions. However, if we arrange
things properly-the zig point must lie “beyond” the intersections with the
other lines-that’s all we lose; that is, we lose only two regions per line. Thus Exercise 18 has the
details.
Z, = Lz,-2n = 2n(2n+1)/2+1-2n
= 2n2-n+l, for n 3 0. (1.7)
Comparing the closed forms (1.6) and (1.7), we find that for large n,
L, N in’,
Z, - 2n2;
so we get about four times as many regions with bent lines as with straight
lines. (In later chapters we’ll be discussing how to analyze the approximate