chap1.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Chapter 1 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib

\pageno=1
\beginchapter 1 Recurrent Problems

THIS CHAPTER EXPLORES 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 {\it "recurrence"}, in which
the solution to each problem depends on the solutions to smaller instances of
the same problem.


\beginsection 1.1 The Tower of Hanoi

Let's look first at a neat little puzzle called the "Tower of Hanoi",
"!Hanoi, Tower of"
invented by the French mathematician Edouard "Lucas" in 1883.
We are given a tower of eight disks,
\g Raise your hand if~you've never seen~this.\par
 OK, the rest of you can cut to equation~\equ(1.1).\g
initially stacked in decreasing size on one of three pegs:
\begindisplay
\unitlength=1in
\beginpicture(2.8,1.5)(0,0)
\put(0,0){\line(0,1){1.5}}
\put(0,0){\line(1,0){2.8}}
\put(2.8,1.5){\line(0,-1){1.5}}
\put(2.8,1.5){\line(-1,0){2.8}}
%\put(2.6,0.2){\llap{(woodcut from 1883)}}
\endpicture
\enddisplay
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 [|lucas-recr|]
 furnished his toy with a romantic legend about a much larger
"Tower of Brahma", which supposedly has 64~disks of pure gold
\g Gold\dash---wow.\par Are our disks made of concrete?\g
resting on three 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.

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 {\sc look at "small cases"} first. It's easy to
"!thinking big"
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":
{\sc "name and conquer"}. Let's say that $T_n$ is the minimum number
of moves that will transfer $n$ disks from one peg to another under
Lucas's rules. Then $T_1$ is obviously~$1$, and $T_2=3$.

We can also get another piece of data for free, by considering the
smallest case of all: Clearly $T_0=0$, because no moves at all are needed to
transfer a tower of $n=0$ disks! Smart mathematicians
"!null case" "!empty case" "!generalize downwards"
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
"!thinking big"
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_{n-1}$ moves),
then move the largest (requiring one move),
and finally transfer the $n-1$ smallest back onto the largest
(requiring another $T_{n-1}$ moves).
Thus we can transfer $n$~disks (for $n>0$) in at most $2T_{n-1}+1$ moves:
\begindisplay
 T_n	\leq 2T_{n-1} + 1 \,, \qquad\hbox{for $n>0$.}
\enddisplay
This formula uses `$\,\leq\,$' instead of `$\,=\,$' because our construction
proves only that $2T_{n-1}+1$ moves suffice; we haven't shown that $2T_{n-1}+1$
moves are necessary. A clever person might be able to think of a shortcut.

But is there a better way? Actually no.
\g Most of the published ``solutions'' to Lucas's problem, like the
early one of Allardice and Fraser~[|allardice|], fail to explain why
$T_n$ must be $\ge 2T_{n-1}+1$.\g
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_{n-1}$ 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_{n-1}$ moves.
Hence
\begindisplay
 T_n	\geq 2T_{n-1} + 1 \,, \qquad\hbox{for $n>0$.}
\enddisplay
These two inequalities, together with the trivial solution for $n=0$, yield
\begindisplay
\eqalign{T_0&=0 \,;\cr
   T_n	&= 2T_{n-1} + 1 \,, \qquad\hbox{for $n>0$.}\cr
}\eqno\eqref|hanoi-rec|
\enddisplay
(Notice that these formulas are consistent with the known values $T_1=1$
and $T_2=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 \thiseq\ is called a {\it "recurrence"\/}
\g Yeah, yeah\thinspace\dots\ I~seen that word before.\g
(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_n$ 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 {\it "solution" to the recurrence\/} would
make us much happier. That
is, we'd like a nice, neat, ``"closed form"'' for~$T_n$
that lets us compute it quickly, even for large~$n$.
With a closed form, we can understand what $T_n$ 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_3=2\cdt3+1=7$;
$T_4 = 2 \cdt 7 + 1 = 15$;
$T_5 = 2 \cdt 15 + 1 = 31$;
$T_6 = 2 \cdt 31 + 1 = 63$.
Aha! It certainly looks as if
\begindisplay
T_n= 2^n-1 \,, \qquad\hbox{for $n \geq 0$.}\eqno\eqref|hanoi-sol|
\enddisplay
At least this works for $n\le6$.

{\it Mathematical "induction"\/} is a general way to prove that some statement
about the integer~$n$ is true for all $n\ge n_0$. First we prove the statement
\g\vskip18pt "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)\newline
and that from each rung we can climb up to the next one (the
induction).\g
when $n$ has its smallest value, $n_0$; this is called the {\it basis}.
"!basis for induction"
Then we prove the statement for $n>n_0$, assuming that it has already been proved
for all values between $n_0$ and $n-1$, inclusive;
this is called the {\it 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, \eq(|hanoi-sol|) follows easily from \eq(|hanoi-rec|):
The basis is trivial, since $T_0=2^0-1=0$. And the induction follows for
$n>0$ if we assume that \thiseq\ holds when $n$ is replaced by~$n-1$:
\begindisplay
T_n &=2T_{n-1} + 1 =2(2^{n-1}-1) + 1 =2^n - 1 \,.
\enddisplay
Hence~\thiseq~holds for~$n$ as well. Good! Our
quest for~$T_n$ has ended successfully.

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 $2^{64}-1$ 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 $2^8-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_n$
we go through three stages:
\smallskip
\item 1
Look at small cases.
This gives us insight into the problem and helps us in stages 2~and~3.

\item 2
Find and prove
\g What is a "proof"? ``One half of one percent pure alcohol.''\g
a mathematical expression for the quantity of interest.
For the Tower of Hanoi, this is the recurrence~\eq(|hanoi-rec|)
that allows us, given the inclination, to compute~$T_n$ for any~$n$.

\item 3
Find and prove a closed form for our mathematical expression.
For the Tower of Hanoi, this is the recurrence solution~\eq(|hanoi-sol|).

\smallskip\noindent
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 {\it without\/} being clairvoyant. For example, we'll see
that recurrence \eq(|hanoi-rec|) can be simplified by adding~$1$ to both
sides of the equations:
\begindisplay
\eqalign{T_0+1&=1 \,;\cr
   T_n+1&=2T_{n-1} + 2 \,, \qquad\hbox{for $n>0$.}\cr
}
\enddisplay
Now if we let $U_n=T_n+1$, we have
\g Interesting: We get rid of the $+1$ in \eq(|hanoi-rec|)
by adding, not by~subtracting.\g
\begindisplay
\eqalign{U_0&=1 \,;\cr
   U_n	&= 2U_{n-1}\,, \qquad\hbox{for $n>0$.}\cr
}\eqno
\enddisplay
It doesn't take genius to discover that the solution to {\it this\/}
recurrence is just $U_n=2^n$; hence $T_n=2^n-1$. Even a computer
could discover this.
%could discover this, for we will discuss a mechanical technique that
%suggests dividing both sides of \thiseq\ by~$2^n$. Then we find
%\begindisplay
%\eqalign{U_0/2^0&=1 \,;\cr
%   U_n/2^n&=U_{n-1}/2^{n-1}\,, \qquad\hbox{for $n>0$;}\cr
%}
%\enddisplay
%so if $V_n=U_n/2^n$ we have
%\begindisplay
%\eqalign{V_0&=1 \,;\cr
%   V_n	&= V_{n-1}\,, \qquad\hbox{for $n>0$.}\cr
%}\eqno
%\enddisplay
%This is a recurrence that doesn't appear in many textbooks, but its
%\g The author jests.\g
%solution is well known.


\beginsection 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_n$ of "regions" defined by $n$ "lines in
the plane"? This problem was first solved in 1826, by the Swiss mathematician
Jacob "Steiner"~[|steiner|].
\g(A pizza with Swiss cheese?)\g

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:
\begindisplay
\unitlength=2pt
\beginpicture(150,36)(0,8)
\put(0,0){\beginpicture(30,35)(-15,0)
	\put(0,8){\makebox(0,0){$L_0=1$}}
	\put(0,30){\makebox(0,0){1}}
	\endpicture}
\put(50,0){\beginpicture(30,35)(-15,0)
	\put(0,8){\makebox(0,0){$L_1=2$}}
	\put(-15,25){\line(3,1){30}}
	\put(-5,36){\makebox(0,0){1}}
	\put(5,24){\makebox(0,0){2}}
	\endpicture}
\put(100,0){\beginpicture(30,35)(-15,0)
	\put(0,8){\makebox(0,0){$L_2=4$}}
	\put(-5,15){\line(1,3){10}}
	\put(-15,25){\line(3,1){30}}
	\put(-6,35){\makebox(0,0){1}}
	\put(11,40){\makebox(0,0){2}}
	\put(6,23){\makebox(0,0){3}}
	\put(-9,20){\makebox(0,0){4}}
	\endpicture}
\endpicture
\enddisplay
(Each line extends infinitely in both directions.)

Sure, we think, $L_n = 2^n$; of course!
Adding a new line simply doubles the number of regions.
Unfortunately this is wrong.
We could achieve the doubling if the $n$th 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".
\g 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.)\g
(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\dash---the thick one in the diagram
below\dash---we soon find that it can split at most three of the old regions,
no matter how we've placed the first two lines:
\begindisplay
\unitlength=2pt
\beginpicture(70,30)(-10,0)
	\put(-8,3){\line(3,1){60}}
	\put(27,0){\line(1,3){10}}
\thicklines
	\put(-10,13){\line(6,-1){70}}
\put(42,26){\makebox(0,0){2}}