chap1.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\kern-1ptPlugging the constant function $f(n)\kern-1pt=\kern-1pt1$ into
\eq(|gen-jos-rec|) says~that
\begindisplay
1&=\alpha;\cr
1&=2\cdt1+\beta;\cr
1&=2\cdt1+\gamma;
\enddisplay
hence the values $(\alpha,\beta,\gamma)=(1,-1,-1)$ satisfying these
equations will yield
$A(n)-B(n)-C(n)=f(n)=1$. Similarly, we can plug in $f(n)=n$:
\begindisplay
1&=\alpha;\cr
2n&=2\cdt n+\beta;\cr
2n+1&=2\cdt n+\gamma;
\enddisplay
These equations hold for all $n$
when $\alpha=1$, $\beta=0$, and $\gamma=1$, so
we don't need to prove by induction that these parameters will yield
$f(n)=n$. We already {\it know\/} that $f(n)=n$ will be the solution
in such a case, because the recurrence \eq(|gen-jos-rec|)
uniquely defines $f(n)$ for every value of~$n$.

And now we're essentially done! We have shown that the functions $A(n)$,
$B(n)$, and $C(n)$ of \eq(|gen-jos-form|), which solve \eq(|gen-jos-rec|)
in general, satisfy the equations
\begindisplay \postdisplaypenalty=-10
A(n)&=2^m\,,\qquad\hbox{where $n=2^m+l$ and $0\le l<2^m$};\cr
A(n)-B(n)-C(n)&=1\,;\cr
A(n)+C(n)&=n\,.\cr
\enddisplay
Our conjectures in \eq(|gen-jos-sol|) follow immediately, since we can
solve these equations to get
$C(n)=n-A(n)=l$ and $B(n)=A(n)-1-C(n)=2^m-1-l$.

This approach illustrates a surprisingly useful {\it "repertoire method"\/}
\g Beware: The authors are expecting us to figure out the idea of the
repertoire method from seat-of-the-pants examples, instead of giving us a
top-down presentation. The
method works best with recurrences that are ``linear,\qback''
in the sense that the solutions can be expressed as a sum
of arbitrary parameters multiplied by functions of\/~$n$, as in \eq(|gen-jos-form|).
Equation \eq(|gen-jos-form|) is the key.\g
for solving recurrences. First we find settings of general parameters
for which we know the solution; this gives us a repertoire of special
cases that we can solve. Then we obtain the general case by combining
the special cases. We need as many independent special solutions
as there are independent parameters (in this case three, for
$\alpha$, $\beta$, and $\gamma$). Exercises 16 and~20 provide further
examples of the repertoire approach.

We know that the original $J$-recurrence has a magical solution,
in binary:
\begindisplay
 J\bigl((b_m\, b_{m-1} \ldots b_1\, b_0)_2\bigr)
	= (b_{m-1} \ldots b_1\, b_0\, b_m)_2 \,, \qquad\hbox{where $b_m=1$.}
\enddisplay
Does the generalized Josephus recurrence admit of such magic?

Sure, why not?
We can rewrite the generalized recurrence~\eq(|gen-jos-rec|) as
\begindisplay
\eqalign{f(1)	&= \alpha \,; \cr
f(2n+j)	&= 2f(n) + \beta_j \,,
			\qquad\hbox{for $j=0,1$\quad and \quad $n \geq 1$,}}
\eqno\eqref|gen-jos-rec-mod|
\enddisplay
if we let $\beta_0=\beta$ and $\beta_1=\gamma$. And this recurrence
unfolds, binary-wise:
\begindisplay
f\bigl((b_m\, b_{m-1} \ldots b_1\, b_0)_2\bigr)
	&= 2f\bigl((b_m\, b_{m-1} \ldots b_1)_2\bigr) + \beta_{b_0} \cr
	&= 4f\bigl((b_m\, b_{m-1} \ldots b_2)_2\bigr) + 2\beta_{b_1}
							+ \beta_{b_0} \cr
	&\qquad\qquad\vdots\cr
	&= 2^m f\bigl((b_m)_2\bigr){+} 2^{m-1}\beta_{b_{m-1}} {+}\cdots
				{+} 2\beta_{b_1} {+} \beta_{b_0} \cr
	&= 2^m \alpha \,+\, 2^{m-1}\beta_{b_{m-1}} \,+\, \cdots
				\,+\, 2\beta_{b_1} \,+\, \beta_{b_0} \,.
\enddisplay
Suppose we now relax the radix~$2$ notation to allow arbitrary digits
\g(`relax' $=$ `destroy')\g
instead of just $0$~and~$1$.
The derivation above tells us that
\begindisplay
f\bigl((b_m\, b_{m-1} \ldots b_1\, b_0)_2\bigr)
	= (\alpha\, \beta_{b_{m-1}}\, \beta_{b_{m-2}}
				\ldots \beta_{b_1}\, \beta_{b_0})_2 \,.
\eqno
\enddisplay
\g \vskip60ptI think I get it:\par
The binary representations of $A(n)$, $B(n)$,
and $C(n)$ have $1$'s in different positions.\g
Nice. We would have seen this pattern
 earlier if we had written \eq(|alpha-beta-gamma|)
in another way:
\begindisplay \advance\abovedisplayskip 2pt
\def\hline{\omit&height2pt\cr\noalign{\hrule}\omit&height2pt\cr}
\vbox{\offinterlineskip\halign{\strut\hfill$#$\ &\vrule#\ &&\ \hfil$#$\cr
n	&&		&&\hidewidth f(n)\cr
\hline
1	&& 		&&		&&\alpha\cr
\hline
2	&&		&& 2\alpha	&+& \beta \cr
3	&&		&& 2\alpha	&+& \gamma \cr
\hline
4	&& 4\alpha	&+& 2\beta	&+& \beta \cr
5	&& 4\alpha	&+& 2\beta	&+& \gamma \cr
6	&& 4\alpha	&+& 2\gamma	&+& \beta \cr
7	&& 4\alpha	&+& 2\gamma	&+& \gamma \cr}}
\enddisplay

For example, when $n=100=(1100100)_2$, our original Josephus values
$\alpha=1$, $\beta=-1$, and~$\gamma=1$ yield
\begindisplay
\vbox{\offinterlineskip\halign{\bigstrut\hfill$#=$&&\quad\hfil$#$\cr
n	& (\; 1	& 1	& 0	& 0	& 1	& 0	& 0 \;)_2
							&=& 100 \cr
\noalign{\vskip2pt\hrule\vskip2pt}
f(n)	& (\; 1	& 1	& -1	& -1	& 1	& -1	& -1 \;)_2\cr
	& +64	& +32	& -16	& -8	& +4	& -2	& -1\phantom{\;)_2}
							&=& 73\cr}}
\enddisplay
as before. The cyclic-shift property follows because each block of binary
digits $(1\,0\,\ldots\,0\,0)_2$ in the representation of $n$ is
transformed into
\begindisplay
(1\,{-1}\,\ldots\,{-1}\,{-1})_2=(0\,0\,\ldots\,0\,1)_2\,.
\enddisplay

So our change of notation has given us the compact solution~\thiseq\
\g\noindent\llap{``}There are two kinds of "generalization"s.
One is cheap and~the other
"!philosophy"
is valuable.\par It is easy to generalize by diluting a little idea
with a big~terminology.\par It is much more difficult to prepare a
refined and condensed extract from several good ingredients.''\par
\noindent\hfill\dash---G. "P\'olya"~[|polya|]\g % p30
to the general recurrence \eq(|gen-jos-rec-mod|).
If we're really uninhibited we can now generalize even more.
The recurrence
\begindisplay
\vcenter{\openup\jot
 \halign{$\hfil#$&${}#\hfil$&\qquad#\hfil\cr
 f(j)	&= \alpha_j \,,&for $1\le j<d$; \cr
f(dn+j)	&= cf(n) + \beta_j \,,&for $0\le j<d$\quad and \quad $n \geq 1$,\cr}}
\eqno
\enddisplay
is the same as the previous one
except that we start with numbers in "radix~$d$" and produce
values in radix~$c$.
That is, it has the radix-changing solution
\begindisplay
f\bigl( (b_m\, b_{m-1} \ldots b_1\, b_0)_d \bigr)
	= (\alpha_{b_m}\, \beta_{b_{m-1}}\, \beta_{b_{m-2}}
		\ldots \beta_{b_1}\, \beta_{b_0})_c \,.
\eqno\eqref|d-to-c|
\enddisplay
For example, suppose that by some stroke of luck we're given the recurrence
\begindisplay
f(1)	&= 34 \,, \cr
f(2)	&= 5 \,, \cr
f(3n)	&= 10f(n) + 76 \,, \qquad\hbox{for $n \geq 1$,} \cr
f(3n+1)	&= 10f(n) - 2 \,, \qquad\nullnum\hbox{for $n \geq 1$,} \cr
f(3n+2)	&= 10f(n) + 8 \,, \qquad\nullnum\hbox{for $n \geq 1$,}
\enddisplay
and suppose we want to compute~$f(19)$.
\g Perhaps this was a stroke of \undertext{bad} luck.\g
Here we have $d=3$ and~$c=10$.
Now $19 = (201)_3$, and the radix-changing solution tells us
to perform a digit-by-digit replacement from radix~$3$ to radix~$10$.
So the leading~$2$ becomes a~$5$,
and the $0$~and~$1$ become $76$~and~$-2$, giving
\begindisplay
f(19)=f\bigl((201)_3\bigr)=(5\,\,76\,\,{-2})_{10}=1258\,,
\enddisplay
which is our answer.

Thus Josephus and the Jewish--Roman war
\g\null\vskip-2\baselineskip But in general I'm against recurrences of war.\g
have led us to some interesting general recurrences.

\beginexercises

\subhead \kern-.05em Warmups

\ex:
All "horses" are the same color; we can prove this by "induction"
\g Please do all the warmups in all the chapters!\par
\hfill\dash---The Mgm't\g
on the number of horses in a given set. Here's how:
``If there's just one horse then it's the same color as itself,
so the basis is trivial.
For the induction step,
assume that there are $n$~horses numbered $1$~to~$n$.
By the induc\-tion hypothesis, horses
$1$~through $n-1$ are the same color,
and similarly horses $2$~through $n$ are the same color.
But the middle horses, $2$~through $n-1$, can't change color
when they're in different groups;
these are horses, not chameleons.
So horses $1$~and~$n$ must be
the same color as well, by transitivity.
Thus all $n$ horses are the same color; QED.'' \
What, if anything, is wrong with this reasoning?
\answer The proof is fine except when $n=2$. If all sets of two horses
have horses of the same color, the statement is true for any number of horses.
\source{"P\'olya" [|polya|, p.~120].}

\ex:
Find the shortest sequence of moves that transfers a tower of $n$ disks
"!tower of Hanoi, variations on"
from the left peg~A to the right peg~B, if direct moves
between A and~B are dis\-allowed. (Each
move must be to or from the middle peg. As usual, a larger disk
must never appear above a smaller one.)
\answer If $X_n$ is the number of moves, we have $X_0=0$ and
$X_n=X_{n-1}+1+X_{n-1}+1+X_{n-1}$ when $n>0$. It follows (for example
by adding~$1$ to both sides) that $X_n=3^n-1$.
\ (After $\half X_n$ moves, it turns out that the entire tower will
be on the middle peg, halfway home!)
\source{"Scorer", "Grundy", and "Smith" [|scorer|].}

\ex: 
Show that, in the process of transferring a tower under the restrictions
of the preceding exercise, we will actually encounter
every properly stacked arrangement of $n$ disks on three pegs.
\answer There are $3^n$ possible arrangements, since each disk can be
on any of the pegs. We must hit them all, since the shortest solution
takes $3^n-1$ moves. \ (This construction is equivalent to a
``ternary "Gray code",\qback'' which runs through all numbers
from $(0\ldots0)_3$ to $(2\ldots2)_3$,
changing only one digit at a time.)

\ex:
Are there any starting and ending configurations of $n$ disks on three
pegs that are more than $2^n-1$ moves apart, under Lucas's original rules?
\answer No. If the largest disk doesn't have to move, $2^{n-1}-1$ moves
will suffice (by induction); otherwise $(2^{n-1}-1)+1+(2^{n-1}-1)$ will
suffice (again by induction).

\ex:
A ``"Venn diagram"'' with three overlapping circles is often used to
illustrate the eight possible subsets associated with three given sets:
\begindisplay
\unitlength=1pt
\beginpicture(64,65)(-32,-20)
	\put(-12,0){\circle{40}}
	\put(+12,0){\circle{40}}
	\put(0,20.8){\circle{40}}
	\put(0,24.2){\hbox to0pt{\hss$A$\hss}}
	\put(-13,-5.4){\vbox to0pt{\vss\llap{$B$}}}
	\put(+13,-5.4){\vbox to0pt{\vss\rlap{$C$}}}
\endpicture
\enddisplay
Can the sixteen possibilities that arise with four given sets be
illustrated by four overlapping circles?
\answer No; different circles can intersect in at most two points, so the
\g The number of intersection points turns out to give the whole story;
convexity was a red herring.\g%
fourth circle can increase the number of regions to at most~14.
However, it is possible to do the job with ovals:
\begindisplay
\unitlength=4pt
\beginpicture(15,15)(0,0)
\put(10,8.5){\oval(10,13)}
\put(7,7.5){\oval(10,13)}
\put(6.5,5){\oval(13,10)}
\put(7.5,8){\oval(13,10)}
\endpicture
\enddisplay
"Venn" [|venn|] claimed that there is no way to do the five-set case with
ellipses, but a five-set construction with ellipses was found by
"Gr\"unbaum" [|gruenbaum|].
\source{"Venn" [|venn|].}

\ex:
Some of the "regions" defined by $n$ lines in the plane are infinite,
while others are bounded. What's the maximum possible number of bounded
regions?
\answer If the $n$th line intersects the previous lines in $k>0$ distinct
\g This answer assumes that $n>0$.\g
points, we get $k-1$ new bounded regions (assuming that none of the previous
lines were mutually parallel) and two new infinite regions. Hence
the maximum number of bounded regions is
$(n{-}2)+(n{-}3)+@\cdots=S_{n-2}=(n{-}1)(n{-}2)/2=L_n-2n$.
\source{"Steiner" [|steiner|]; "Roberts"~[|roberts|].}

\ex:
Let $H(n)=J(n+1)-J(n)$. Equation \equ(1.|josephus-rec|) tells us that
$H(2n)=2$, and $H(2n+1)=J(2n+2)-J(2n+1)
 =\bigl(2\mkern1muJ(n+1)-1\bigr)-\bigl(2\mkern1muJ(n)+1\bigr)=2H(n)-2$, for all $n\ge1$.
Therefore it seems possible to prove that $H(n)=2$
for all~$n$, by induction on~$n$. What's wrong here?
\answer The basis is unproved; and in fact, $H(1)\ne2$.

\subhead Homework exercises

\ex:\exref|lyness|%
Solve the recurrence
\begindisplay
Q_0&=\alpha\,;\qquad Q_1=\beta\,;\cr
Q_n&=(1+Q_{n-1})/Q_{n-2}\,, \qquad\hbox{for $n>1$.}\cr
\enddisplay
Assume that $Q_n\ne 0$ for all $n\ge0$. \Hint: $Q_4=(1+\alpha)/\beta$.
\answer $Q_2=(1+\beta)/\alpha$; $Q_3=(1+\alpha+\beta)/\alpha\beta$;
$Q_4=(1+\alpha)/\beta$; $Q_5=\alpha$; $Q_6=\beta$. So the sequence is
periodic!
\source{"Gauss" [|gauss-penta|].}

\ex:
Sometimes it's possible to use "induction" backwards,
\g\dots\ now that's a horse of a different color.\g
 proving things from
$n$ to $n-1$ instead of vice versa! For example, consider the statement
\begindisplay
P(n):\quad x_1\ldots x_n \le \left(x_1+\cdots+x_n\over n\right)^n\,,\quad
 \hbox{if $x_1,\ldots,x_n\ge 0$.}
\enddisplay
This is true when $n=2$, since $(x_1+x_2)^2-4x_1x_2=(x_1-x_2)^2\ge0$.
\smallskip
\itemitem a
By setting $x_n=(x_1+\cdots+x_{n-1})/(n-1)$, prove that $P(n)$ implies~$P(n-1)$
whenever $n>1$.
\itemitem b