chap1.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\put(26.5,11){\makebox(0,0){4a}}
\put(19,3.5){\makebox(0,0){4b}}
\put(34,1){\makebox(0,0){3b}}
\put(-8,8){\makebox(0,0){1b}}
\put(3.67,14.89){\makebox(0,0){1a}}
\put(36.79,9.37){\makebox(0,0){3a}}
\endpicture
\enddisplay
Thus $L_3 = 4+3 = 7$ is the best we can do.

And after some thought we realize the appropriate generalization.
The $n$th~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\le n$.
We have established the upper bound
\begindisplay
 L_n	\leq L_{n-1} + n \,, \qquad\hbox{for $n >0$.}
\enddisplay
Furthermore it's easy to show by induction
that we can achieve equality in this formula.
We simply place the $n$th 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 through any of the existing intersection points (hence
it intersects them all in different places). The recurrence is therefore
\begindisplay
\eqalign{L_0	&=1 \,;\cr
L_n	&=L_{n-1} + n \,, \qquad\hbox{for $n >0$.}}\eqno\eqref|lines-rec|
\enddisplay
The known values of $L_1$, $L_2$, and $L_3$ 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$,
\dots\ 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:
\begindisplay
L_n	&= L_{n-1} + n \cr
	&= L_{n-2} + (n-1) + n \cr
\noalign{\g Unfolding?\newline I'd call this\newline``plugging in.\qback''\g}
	&= L_{n-3} + (n-2) + (n-1) + n \cr
	&\qquad\qquad\vdots\cr
	&= L_0 + 1 + 2 + \cdots + (n-2) + (n-1) + n \cr
\noalign{\vskip2pt}
	&= 1\;+\;S_n\,,\qquad\hbox{where $S_n=1+2+3+\cdots+(n-1)+n$.}
\enddisplay
In other words, $L_n$~is one more than the sum~$S_n$ of the first $n$~positive
integers.

The quantity~$S_n$ 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:
\begindisplay 
\vbox{\halign{\span\tablepreamble\cr
n&&1&2&3&4&5&6&7&8&9&10&11&12&13&14\cr
\noalign{\hrule}
S_n&&1&3&6&10&15&21&28&36&45&55&66&78&91&105\cr}}
\enddisplay
These values are also called the {\it"triangular numbers"}, because
$S_n$ is the number of "bowling pins" in
an $n$-row triangular array.
For example, the usual four-row array
\unitlength=1.732pt
\beginpicture(10,0)(-4.75,0)
\put(0,-.732){\disk{1}}
\put(-1.5,1.000){\disk{1}}
\put(1.5,1.000){\disk{1}}
\put(-3,2.732){\disk{1}}
\put(0,2.732){\disk{1}}
\put(3,2.732){\disk{1}}
\put(-4.5,4.464){\disk{1}}
\put(-1.5,4.464){\disk{1}}
\put(1.5,4.464){\disk{1}}
\put(4.5,4.464){\disk{1}}
\endpicture
\ has $S_4 = 10$ pins.

To evaluate~$S_n$ we can use a trick that "Gauss" reportedly came up with
"!sum of consecutive integers"
in 1786, when he was nine years old~[|gauss-bio|]
(see also "Euler" [|euler-algebra|, part~1, \S415]):%
\g It seems a lot of stuff is attributed to~Gauss\dash---\newline
either he was really smart or he had a great press agent.\par
\vskip24pt\par
Maybe he just had a magnetic personality.\g
\begindisplay 
\vbox{\offinterlineskip\halign{\bigstrut\hfill$#$\ &&\ \hfil$#$\hfil\cr
S_n\;=&1&+&2&+&3&+&\cdots&+&(n-1)&+&n\cr
{}+S_n\;=&n&+&(n-1)&+&(n-2)&+&\cdots&+&2&+&1\cr
\noalign{\vskip1pt\hrule}
2S_n\;=&(n+1)&+&(n+1)&+&(n+1)&+&\cdots&+&(n+1)&+&(n+1)\cr}}
\enddisplay
We merely add $S_n$ to its reversal, so that each of the $n$ columns on
the right sums to $n+1$.
Simplifying,
\begindisplay
S_n	= {n(n+1)\over2} \,, \qquad\hbox{for $n \geq 0$.}\eqno
\enddisplay
OK, we have our solution:
\g 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.\g
\begindisplay
L_n= {n(n+1)\over2} + 1 \,, \qquad\hbox{for $n \geq 0$.}\eqno\eqref|lines-sol|
\enddisplay

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
\begindisplay
\textstyle L_n = L_{n-1} + n = \bigl(\half(n-1)n + 1\bigr) + n
 = \half n(n+1) + 1\,.
\enddisplay
Now there can be no doubt about the closed form \thiseq.

Incidentally we've been talking about ``"closed form"s''
\g When in doubt, look at the words. Why is it ``closed,\qback'' as opposed to
``open''? What image does it bring to mind?\par Answer: The equation is
``closed,\qback''
not defined in terms of itself\dash---not leading to recurrence.
The case is ``closed''\dash---it won't happen again. Metaphors are the key.\g
without explicitly saying what we mean.
Usually it's pretty clear.
Recurrences like \eq(|hanoi-rec|) and~\eq(|lines-rec|)
are not in closed form\dash---%
they express a quantity in terms of itself;
but solutions like \eq(|hanoi-sol|) and~\eq(|lines-sol|) are.
Sums like $1 + 2 + \cdots + n$ are not in closed form\dash---%
they cheat by using `$\,\cdots\,$';
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^n-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\cdt2\cdt\ldots \cdt 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".\qback''
\g Is ``zig'' a technical term?\g
What is the maximum number $Z_n$ of regions
determined by $n$~such bent lines in the plane?
We might expect $Z_n$ to be about twice as big as $L_n$, or maybe
three times as big. Let's see:
\begindisplay
\unitlength=2pt
\beginpicture(120,40)(0,7)
\put(0,0){\beginpicture(40,40)(-20,0)
	\put(0,7){\makebox(0,0){$Z_1=2$}}
	\put(-18,30){\line(3,1){36}}
	\put(-18,30){\line(3,-1){36}}
	\put(-9,18){\makebox(0,0){1}}
	\put(10,30){\makebox(0,0){2}}
	\endpicture}
\put(80,0){\beginpicture(40,40)(-20,0)
	\put(0,7){\makebox(0,0){$Z_2=7$}}
	\put(0,12){\line(1,3){12}}
	\put(0,12){\line(-1,3){12}}
	\put(-18,30){\line(3,1){36}}
	\put(-18,30){\line(3,-1){36}}
	\put(-9,20){\makebox(0,0){1}}
	\put(0,44){\makebox(0,0){2}}
	\put(15,45){\makebox(0,0){3}}
	\put(13,30){\makebox(0,0){4}}
	\put(0,20){\makebox(0,0){5}}
	\put(-9,30){\makebox(0,0){6}}
	\put(0,30){\makebox(0,0){7}}
	\endpicture}
\endpicture
\enddisplay

From these small cases, and after a little thought,
\g\dots\ and a little afterthought\dots\g
we realize that a bent line is like two straight lines
except that regions merge when the ``two'' lines
don't extend past their intersection point.
\begindisplay
\unitlength=2pt
\beginpicture(80,36)(-40,-18)
\put(0,0){\line(3,1){30}}
\put(0,0){\line(3,-1){30}}
\multiput(-28.5,-9.5)(3,1){10}{\disk{.5}}
\multiput(-28.5,9.5)(3,-1){10}{\disk{.5}}
\put(25,0){\makebox(0,0){1}}
\put(0,-11){\makebox(0,0){2}}
\put(-25,0){\makebox(0,0){3}}
\put(0,11){\makebox(0,0){4}}
\endpicture
\enddisplay
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\dash---%
the zig point must lie ``beyond''
the intersections with the other lines\dash---%
that's all we lose;
that is, we lose only two regions per line.
\g Exercise |zig| has the details.\g
Thus
\begindisplay
Z_n= L_{2n} - 2n& =2n(2n+1)/2 + 1 - 2n\cr
	&= 2n^2 - n + 1\,,\qquad\hbox{for $n \geq 0$.}\eqno\eqref|zn-def|
\enddisplay
Comparing the closed forms \eq(|lines-sol|) and~\thiseq,
we find that for large~$n$,
\begindisplay
L_n&\sim\textstyle\half n^2 \,,\cr
Z_n&\sim 2n^2 \,;
\enddisplay
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 behavior
of integer functions when $n$ is large. The `$\sim$' symbol is defined
in Section~9.1.)

\beginsection 1.3 The Josephus Problem

Our final introductory example is a variant
\g("Ahrens"~[|ahrens|, vol.~2] and
 "Herstein" and~"Kaplansky"~[|herstein-kaplansky|] discuss
 the interesting history of this problem. Josephus himself
 [|josephus-source|] is a bit vague.)\g
 of an ancient problem named
for Flavius "Josephus", a famous historian of the first century. Legend
has it that Josephus
wouldn't have lived to become famous
without his mathematical talents.
During the Jewish--Roman "war",
he was among a band of 41 Jewish rebels trapped in a cave by the Romans.
"!Seaver, George Thomas"
"!Mathews, Edwin Lee: same as Seaver (all the 41s) (also page 41)"
Preferring suicide to capture, the rebels decided to form a circle and,
proceeding around it, to kill every third remaining person until no~one
was left.
But Josephus, along with an unindicted co-conspirator,
wanted none of this suicide nonsense;
so he quickly calculated where he and his friend should stand in
\g\dots thereby saving his tale for us to hear.\g
the vicious circle.

\newdimen\digwd \newdimen\dight \setbox0=\hbox{$0$} \digwd=\wd0 \dight=\ht0
\def\cnum#1{\hbox to0pt{\hss\lower.5\dight\hbox to\digwd{\hss$#1$}\hss}}
In our variation, we start with $n$~people numbered 1~to~$n$ around a circle,
and we eliminate every {\it second\/} remaining person until only one survives.
For example, here's the starting configuration for $n=10$:
\begindisplay
\unitlength=2pt
\beginpicture(40,32)(-20,-16)
\put(0,0){\circle{20}}
\put(0,0){\vector(0,1){9}}
\put(0,14.5){\cnum1}
\put(8.52,11.73){\cnum2}
\put(13.79,4.48){\cnum3}
\put(13.79,-4.48){\cnum4}
\put(8.52,-11.73){\cnum5}
\put(0,-14.5){\cnum6}
\put(-8.52,-11.73){\cnum7}
\put(-13.79,-4.48){\cnum8}
\put(-13.79,4.48){\cnum9}
\put(-8.52,11.73){\cnum{10}}
\endpicture
\enddisplay
The elimination order is $2$,~$4$, $6$, $8$, $10$, $3$, $7$, $1$,~$9$,
so $5$~survives. The problem:
Determine the survivor's number,~$J(n)$.
\g Here's a case where $n=0$ makes no sense.\g

We just saw that $J(10)=5$.
We might conjecture that $J(n)=n/2$ when $n$~is even;
and the case $n=2$ supports the conjecture: $J(2) = 1$.
But a few other small cases dissuade us\dash---%
the conjecture fails for $n=4$ and~$n=6$.
\begindisplay 
\vbox{\halign{\span\tablepreamble\cr
n&&1&2&3&4&5&6\cr
\noalign{\hrule}
J(n)&&1&1&3&1&3&5\cr}}
\enddisplay
It's back to the drawing board; let's try to make a better guess.
\g Even so, a bad guess isn't a waste of time, because it gets us
involved in the problem.\g
Hmmm \dots\ $J(n)$ always seems to be odd.
And in fact, there's a good reason for this:
The first trip around the circle eliminates all the even numbers.
Furthermore, if $n$ itself is an even number, we arrive at
a situation similar to what we began with, except that there are
only half as many people, and their numbers have changed.

So let's suppose that we have $2n$~people originally.
After the first go-round, we're left with
\begindisplay
\unitlength=2pt
\beginpicture(48,31)(-28,-15)
\put(0,0){\circle{20}}
\put(0,0){\vector(0,1){9}}
\put(0,14.5){\cnum1}
\put(8.52,11.73){\cnum3}
\put(13.79,4.48){\cnum5}
\put(13.79,-4.48){\cnum7}
\put(0,-14.5){\cnum{\ldots}}
\put(-13.79,4.48){\cnum{2n-3}}
\put(-8.52,11.73){\cnum{2n-1}}
\endpicture
\enddisplay
and $3$~will be the next to go.
This is just like starting out with $n$~people,
except that each person's number has been doubled and decreased by~$1$.
\g This is the tricky part: We have\smallskip
$J(2n)=$\newline