% Bugs (sigh) in Concrete Math

\input gkpmac
\preprintfalse
\raggedbottom
\def\rightcorner{\vbox to\folioht{\vfil}\relax}
\pageno=627

\def\today{\number\day\
  \ifcase\month\or
  Jan\or Feb\or Mar\or Apr\or May\or Jun\or
  Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi
  \ \number\year}

\def\cutpar{{\parfillskip=0pt\par}}

\beginchapter {} Concrete Mathematics Errata

THIS IS A LIST
\g``And if you happen in reading to finde any more faultes not here
mentioned, as peraduenture you may, \dots\
I trust you will therefore impute no blame either vnto me or to the
Printer, but gently amend and correct them, accepting our good minde,
which was to haue had the booke passed to your handes vtterly
without fault, as touching the Printing.''\par
\hfill\dash---from the first\par
\hfill English edition\par
\hfill of Euclid [80]\g
 of all corrections made to the first printing (August 1988) of
{\sl Concrete Mathematics\/} by Graham, Knuth, and Patashnik.
The second printing (December 1988) incorporates these changes,
so the book is now perfect.

But you may disagree.
To claim a reward for any anomalies you spot that aren't shown here,
please send your comments to D.~E. Knuth, Computer Science Department,
Stanford University, Stanford CA 94305, as soon as possible.

\def\bugonpage#1(#2) \par{\bigbreak
  \vbox{\hrule width\hsize}
  \line{\lower3.5pt\vbox to13pt{}Page #1\hfil(#2)}%
  \nobreak\vskip-5pt
  \vbox{\hrule width\hsize}
  \nobreak\medskip}

\def\bib#1 {\noindent\hbox to\parindent{\bf#1\hss}\hangindent\parindent}

\bugonpage viii, lines 3--6 from the bottom (15 Sep 88)

{\tolerance=9999 \noindent
and developed with the help of a committee that included
B.~"Beeton", R.\thinspace P. "Boas", L.\thinspace K. "Durst",
D.\thinspace E. "Knuth",
P.~"Murdock", R.\thinspace S. "Palais", P.~"Renz",
 E.~"Swanson", S.\thinspace B. "Whidden",
and W.\thinspace B. "Woolf". The underlying philosophy of
Zapf's design is
to capture the flavor of mathematics as it might\cutpar}

\bugonpage ix, lines 10 and 11 (3 Oct 88)

\noindent
and Euler Script Capitals ($\scr A\,B\,C$ through $\scr X\,Y\,Z$), as
well as Euler Greek ($A\alpha\,B\beta\,\Gamma\gamma$ through
$X\chi\,\Psi\psi\,\Omega\omega$) and special symbols such as
$\wp$ and~$\aleph$. We are\cutpar

\bugonpage xi, lines 10--15 (22 Oct 88)

\begingroup \advance\baselineskip 7pt plus 1pt \advance\lineskip 7pt plus 1pt
\advance\lineskiplimit7pt
\halign to\hsize{\displaymath#$\hfill\tabskip10pt plus20pt&
 #\hfil&\hfil#\tabskip0pt\cr
\phantom{K(a_1,\ldots,a_n)}
&\phantom{generalized harmonic number: $1/1^x+\cdots+1/n^x$}\cr
\noalign{\vskip-\baselineskip}
[\alpha\dts\beta]&closed interval: the set
 $\{x\mid \alpha\le x\le\beta\}$&73\cr
\[m=n]&$1\,$ if $m=n$, otherwise $0\,$*&24\cr
\[m\divides n]&$1\,$ if $m$ divides $n$, otherwise $0\,$*&102\cr
\[m\edivides n]&$1\,$ if $m$ exactly divides $n$, otherwise $0\,$*&146\cr
\[m\rp n]&$1\,$ if $m$ is relatively prime to $n$, otherwise $0\,$*&115\cr}
\endgroup\bigskip\noindent
\llap{*}In general, if $S$ is any statement that can be true or false, the
bracketed notation
$\[S]$ stands for $1$~if $S$~is true, $0$ otherwise.

\nobreak\medskip
\noindent[Important note to readers of this errata list:
Iverson's convention is to be changed {\sc throughout the book} from
parentheses to brackets.]

\bugonpage xiii, line 13 (26 Sep 88)

\itemitem{6.6}Fibonacci Numbers\qquad276

\bugonpage xiii, line 29 (31 Aug 88)

\itemitem{8.4}Flipping Coins\qquad387

\bugonpage 1, second line before the illustration (24 Oct 88)

\noindent
invented by the French mathematician Edouard "Lucas" in 1883.
We are given\cutpar

\bugonpage 20, line 4 (12 Oct 88)

$m$th person, all the bad guys are first to go. (For example, when $n=3$\cutpar

\bugonpage 20, first line of graffito (23 Oct 88)

\noindent\g Yes, and well~done\g

\bugonpage 24, line 21 (23 Oct 88)

\noindent
book. The idea is simply to enclose a true-or-false statement
in brackets,\cutpar

\bugonpage 27, line 5 (19 Oct 88)

\noindent
currence could be divided by $2^n$. This trick
is a special case of a general\cutpar

\bugonpage 28, line 9 (4 Oct 88)

\noindent
cases gives us some data ($C_1=2$, $C_2=5$, $C_3={26\over3}$)
but doesn't do anything\cutpar

\bugonpage 32, top line, and second line of graffiti (23 Oct 88)

\noindent
Typically we use rule \equ(2.20) either to combine two almost-disjoint
\g\equ(2.20) have been\g
index sets,\cutpar

\bugonpage 44, first line of second graffito (31 Aug 88)

\noindent\g $\hbox{Method 2\/}'\mskip-1mu$:\g

\bugonpage 46, last line of second graffito (19 Sep 88)

\noindent\g sides.)\g

\bugonpage 51, line 7 from the bottom (10 Nov 88)

\noindent
anything else? Well, no, it's often possible to work directly with
factorial\cutpar

\bugonpage 61, line 13 (3 Oct 88)

\noindent
prove that if $J$ and the elements of $\{K_j\mid j\in J\}$ are
any sets of indices such that

\bugonpage 64, lines 13--14 (12 Oct 88)

\hangindent\parindent\textindent{\bf21\hss}%
Evaluate the sums $S_n=\sum_{k=0}^n(-1)^{n-k}$, \ $T_n=\sum_{k=0}^n
(-1)^{n-k}@k$, and $U_n=\sum_{k=0}^n(-1)^{n-k}@k^2$ by the perturbation
method, assuming that $n\ge0$.

\bugonpage 67, first three lines after chapter title (6 Oct 88)

\noindent
WHOLE NUMBERS constitute the backbone of discrete mathematics,
and we often need to convert from fractions or arbitrary real numbers
to integers. Our goal in this chapter is to gain familiarity and fluency
with such conversions\cutpar

\bugonpage 73, lines 14--20 (22 Oct 88)

For our next problem let's consider a handy new notation, suggested by
Lyle "Ramshaw", for "intervals" of the real line:
$[\alpha\dts \beta ]$ denotes the set of real numbers~$x$ such that
$\alpha \leq x \leq \beta$.
This set is called a {\it "closed interval"\/} because
it contains both endpoints $\alpha$~and~$\beta$.
The interval containing neither endpoint, denoted by $(\alpha\dts \beta)$,
consists of all~$x$ such that $\alpha < x < \beta$; this
is called an {\it "open interval"}.
And the intervals $[\alpha\dts \beta)$ and $(\alpha\dts \beta ]$,
which contain just one endpoint, are defined similarly and called
{\it "half-open"}.

\nobreak\medskip
\noindent[The notation for intervals is to be changed {\sc throughout the book}.]

\bugonpage 75, lines 1--2 (7 Oct 88)

The whole setup
can be analyzed systematically if we use the summation techniques
of Chapter~2, taking advantage of
"Iverson's convention" about\cutpar

\bugonpage 80, line 7 (13 Oct 88)

\noindent
$a_n=-2$, $+1$, or~$-\half $ according as $n\bmod3=0$, $1$, or~$2$.
But this recurrence\cutpar

\bugonpage 81, line 15 (5 Oct 88)

\line{\indent
{\bf while} \ $D\le(q-1)n$ \ {\bf do} \
 $D:=\bigl\lceil{q_{\mathstrut}\over q-1}D\bigr\rceil\,$;\hfill
\equ(3.19)}

\bugonpage 88, line 7 from the bottom (22 Oct 88)

\vskip-20pt
\begindisplay
\sum_k\Bigi[k\in\bigl[@
 j\alpha^{-1}\dts(j+v)\alpha^{-1}\bigr)\Bigr]
&=\bigl\lceil(j+v)(a+\alpha')\bigr\rceil-\bigl\lceil j(a+\alpha')\bigr\rceil\cr
\enddisplay

\bugonpage 100, bottom line (23 Oct 88)

\vskip-20pt
\begindisplay
\indent
\bigl\{\,\lfloor n\alpha\rfloor+\lfloor n\beta\rfloor\bigm\vert\hbox{$n>0$}\,\bigr\}\,.
\enddisplay

\bugonpage 109, line 20 (24 Oct 88)

\noindent
is prime. In fact, just about any
computation with it takes a lot of time,\cutpar

\bugonpage 109, bottom line (8 Sep 88)

$\displaystyle
2^{mn}-1=(2^m-1)(2^{m(n-1)}+2^{m(n-2)}+\cdots+1)\,.$

\bugonpage 111, second line of graffito (15 Sep 88)

\noindent \g notation tr\`es simple\g

\bugonpage 116, line 16 (14 Oct 88)

\noindent
$k_pn_p=0$ if and only if $k_p(m_p+n_p)=0$,
when $m_p$ and $n_p$ are nonnegative.

\bugonpage 118, lines 11--13 from the bottom (23 Oct 88)

\vskip-20pt
\begindisplay
(m'+n')(an-bm)+(m+n)(bm'-an')&\ge m'+n'+m+n\,;
\enddisplay
and this is the same as $a+b\ge m'+n'+m+n$ by \equ(4.31).
Either $m$ or $n$ or $m'$ or $n'$
increases at each step, so we must win after at most $a+b$~steps.

\bugonpage 123, line 21 (20 Oct 88)

\noindent
Stern--Brocot representations of rationals. Given $\alpha=m/n$,
we get $\lfloor m/n\rfloor$\cutpar

\bugonpage 125, line 7 from the bottom (18 Oct 88)

\line{$\displaystyle
\indent\indent\iff a\=b\quad\Bigl({\rm mod}\,\,{m\over\gcd(d,m)}\Bigr)\,,
	\quad\hbox{integer $a,b,d,m$}.\hfill\equ(4.39)$}

\bugonpage 143, lines 10 and 11 (2 Oct 88)

\vskip-20pt
\begindisplay \openup3pt
\phantom{n^{p^3}}
	&= n^p \,+\, p^3\hbox{\eulerbf Q}
\enddisplay
for yet another integer~{\eulerbf Q}.
So $p^3$~divides $n^{p^3} \!- n^{p^2}$. This finishes the proof for\cutpar

\bugonpage 146, line 24 (24 Oct 88)

inators are less than~$50$. Is $22\over7$ one of them?

\bugonpage 148, bottom two lines (26 Oct 88)

\hangindent\parindent\textindent{\bf48\hss}%
Generalize "Wilson's theorem" \equ(4.49) by ascertaining the value of
the expression $\bigl(\prod_{1\le n<m,\,n\rp m}n\bigr)\bmod m$, when $m>1$.

\bugonpage 158, second line of graffito (18 Oct 88)

\noindent
\g anyway.)\g

\bugonpage 169, line 6 from the bottom (21 Sep 88)

\noindent to Chu Shih-Chieh
in China as early as 1303. All of the other identities in\cutpar

\bugonpage 180, lines 5--7 from the bottom (26 Oct 88)

\noindent
$m=n=1$ and $q=0$ in~\equ(5.26). Then the identity reads
\begindisplay
\sum_{0\le k\le l}(l-k)k={l+1\choose 3}\,.
\enddisplay
The left side is $l\bigl((l+1)l/2\bigr)-(1^2+2^2+\cdots+l^2)$, so this gives us
a brand new\cutpar

\bugonpage 181, line 9 from the bottom (24 Oct 88)

\vskip-20pt
\begindisplay
 \sum_{k\ge0} {n+k \choose 2k} {2k \choose k} {(-1)^k\over k+1} \,,
					\qquad\hbox{integer $n \geq 0$.}
\enddisplay
[The same change, `$\sum_{k\ge0}$' instead of simply `$\sum_k$', should
be made to the first three sums on page 182, the first three sums on page 183,
and the first two sums in Problem~8 on page 184.]

\bugonpage 183, lines 3 and 4 (4 Oct 88)

\noindent The sum actually does turn out to be~$1$ when $n=0$,
so the correct answer is `$\[n=0]$'.
We must have made a mistake in the previous derivation.

\bugonpage 183, line 3 from the bottom (24 Oct 88)

\vskip-20pt
\begindisplay
\qquad= \sum_{j \geq 0} {j \choose m-1}
  \sum_{\scriptstyle k \geq j-n+1\atop\scriptstyle k\ge0}
 {n+k-1-j \choose 2k}{2k \choose k} {(-1)^k\over k+1} \,.
\enddisplay

\bugonpage 184, lines 8--11 (22 Nov 88)

\noindent
$j-n+1$ superfluous, and we can use the
result of Problem~6. The double sum now comes tumbling down:
\begindisplay
&\sum_{j \geq 0} {j \choose m-1}
  \sum_{\scriptstyle k \geq j-n+1\atop\scriptstyle k\ge0}
  {n+k-1-j \choose 2k}{2k \choose k} {(-1)^k\over k+1}\cr
&\qquad=\sum_{0\le j<n} {j \choose m-1}
 \sum_{k\ge0}{n+k-1-j \choose 2k}{2k \choose k} {(-1)^k\over k+1}\cr
\enddisplay

\bugonpage 184, bottom line (26 Oct 88)

\noindent
[This equation number should be \equ(5.33), not \equ(5.43); all equation
numbers {\sc throughout the rest of the chapter} are ten too high.
However, in these errata we will continue to use the old numbers.]

\bugonpage 186, lines 2 and 3 from the bottom (4 Oct 88)

\vskip-20pt
\begindisplay \openup3pt \postdisplaypenalty=10000
\phantom{\displaystyle{-1/2\choose4}}
 &=\left(-1\over2\right)^{\!4}{1\cdt3\cdt5\cdt7\over1\cdt2\cdt3\cdt4}\cr
 &=\left(-1\over4\right)^{\!4}{1\cdt3\cdt5\cdt7\cdt2\cdt4\cdt6\cdt8 
           \over 1\cdt2\cdt3\cdt4\cdt1\cdt2\cdt3\cdt4}
  =\left(-1\over4\right)^{\!4}{8\choose4}\,.
\enddisplay

\bugonpage 187, line 6 (4 Oct 88)

We can also use Vandermonde's convolution \equ(5.27) to deduce that

\bugonpage 187, line 11 (4 Oct 88)

\noindent
this is what sums to $(-1)^n$.
Hence we have a remarkable property of the\cutpar

\bugonpage 188, line 5 from the bottom (24 Oct 88)

\noindent
have $\Delta f(x)=(-1)(x-1)\_{-2}$,
$\Delta^{2\,} f(x)=(-1)(-2)(x-1)\_{-3}$, and in general

\bugonpage 188, bottom line (24 Oct 88)

\def\chapno{5}\eqcount=50
\vskip-20pt
\begindisplay
\phantom{\sum_k{n\choose k}{(-1)^k\over x+k}}
 &=x^{-1}{x+n\choose n}^{-1}\,,\qquad \hbox{$x\notin\{0,-1,\ldots,-n\}@$}.
\eqno
\enddisplay

\bugonpage 191, line 7 (24 Oct 88)

\noindent
integer. Our derivation
of the formula $\Delta^{n\,}f(0)=c_n$ works in the infinite case,\cutpar

\bugonpage 193, lines 5--7 (24 Oct 88)

 For example, $g(n)$ might be a known function,
and $f(n)$ might be unknown; and we might have found a way to
prove that $g(n)=\sum_k\kern-.34pt{n\choose k}(-1)^k f(k)$. Then
\equ(5.58) lets us
express $f(n)$ as a sum of known values.

\bugonpage 201, line 10 (6 Nov 88)

\noindent
constant term of $\Escr_t(z)^r$ is $r(0+r)^{-1}$, and this
is equal to~$1$ even when $r=0$.)

\bugonpage 201, line 14 (24 Oct 88)

\vskip-20pt
\begindisplay
\Bscr_t(z)^r{\Bscr_t(z)^s\over1-t+t\Bscr_t(z)^{-1}}
&=\sum_{k\ge0}{tk+r\choose k}{r\over tk+r}z^k\,
  \sum_{j\ge0}{t@j+s\choose j}z^j\cr
\enddisplay

\bugonpage 207, line 10 (24 Oct 88)

\vskip-20pt
\begindisplay
\ln(1+z)=z\hyp{1,1\,}2{-z}
&=z\,\sum_{k\ge0}{k!\,k!\over(k+1)!}\,{(-z)^k\over k!}
\enddisplay

\bugonpage 212, line 2 from the bottom (31 Oct 88)

\noindent
hyper\-geometer can read off
the parameters immediately as $F(1,-m;-n;1)$.\cutpar

\bugonpage 213, line 6 from the bottom (30 Oct 88)

\noindent
rather $-@6!/3!=(-4)(-5)(-6)$, according to~\equ(5.105).

\bugonpage 225, line 14 (2 Nov 88)

\vskip-20pt \eqcount=129 \def\chapno{5}
\begindisplay
cT(k)={r(k)\,s(k)\,t(k)\over p(k)}\,,
\eqno
\enddisplay

\bugonpage 225 lines 10 and 11 from the bottom (2 Nov 88)

\noindent
by \equ(5.130) and~\equ(5.129), $r(k)@s(k)/p(k)=
T(k)/\bigl(T(k+1)-T(k)\bigr)$ is a rational function of~$k$,
and $s(k)$ itself must be a quotient of polynomials:

\bugonpage 227, lines 12 and 13 (2 Nov 88)

\noindent
two cases. Either $d=\deg(p)-\deg(R)+1$, which is~$0$;
or $d=-2\beta/\gamma$ where $\beta=-n$ and $\gamma=2$, hence $d=n$.
The first case is nicer, so let's try it first:\cutpar

\bugonpage 227, lines 11 and 12 from the bottom (2 Nov 88)

\vskip-20pt
\begindisplay \openup3pt
cT(k)&={r(k)\,s(k)\,t(k)\over p(k)}\cr
&=k\cdot{(-1)\over n}\cdot{n \choose k}(-1)^k\cr
\enddisplay

\bugonpage 228, line 11 (2 Nov 88)

\vskip-20pt
\begindisplay
cT(k)={1\cdot\bigl(-\half k-{1\over4_{\mathstrut}}\bigr)\cdot{-2@\choose k}\over k+1}
=(-1)^{k-1}{2k+1\over4}\,.
\enddisplay

\bugonpage 234, line 13 (22 Oct 88)

\vskip-20pt
\begindisplay
\hbox{\indent}
\sum_{j=1}^m(-1)^{j+1}{r\choose j}\sum_{k=1}^n{-j+rk+s\choose m-j},
 \qquad\hbox{integers $m,n\ge0$}.
\enddisplay

\bugonpage 242, bottom line (4 Oct 88)

\textindent{\bf97\hss}%
For what values of $n$ is ${2n\choose n}\=(-1)^n$ \tmod{(2n+1)}?

\bugonpage 245, line 8 from the bottom (26 Oct 88)

\noindent
{\it"cycles"\/} instead of subsets. We verbalize
`$n\brack k$' by saying ``$n$~cycle~$k$.\qback''

\bugonpage 248, lines 17--19 (27 Oct 88)

\noindent
These coefficients look suspiciously
like the numbers in Table 244,
reflected between left and right; therefore we can be pretty confident
that the general formula is\g\vskip2pt We'd better define\smallskip
${n\brace k}={n\brack k}=0$\smallskip
when $k<0@$ and $n\ge0$.\g

\bugonpage 252, line 3 (31 Oct 88)

\def\chapno{6}\eqcount=29
\vskip-20pt
\begindisplay
x\_^n>x^n>x\_n\,,\qquad\hbox{for all $x>n>1$}.\eqno
\enddisplay

\bugonpage 253, second line before Section 6.2 (26 Oct 88)

\noindent
both of the recurrences
${n\brack k}=(n-1){n-1\brack k}+{n-1\brack k-1}$ and
${n\brace k}=k{n-1\brace k}+{n-1\brace k-1}$\cutpar

\bugonpage 267, bottom four lines (31 Oct 88)

\noindent
\looseness=-1
If we subtract out the term for $k=0$ and set $x=0$, we get $-T_n$.
So let's do~it:
\begindisplay \openup5pt
T_n&=\biggl({1\over x}-{n!\over x(x+1)\ldots(x+n)}\biggr)\,\bigg\vert_{x=0}\cr
&=\biggl({(x+1)\ldots(x+n)-n!\over x(x+1)\ldots(x+n)}\biggr)\,\bigg\vert_{x=0}\cr
&=\biggl({x^n{n+1\brack n+1}+\cdots+x{n+1\brack2}+{n+1\brack1}-n!
   \over x(x+1)\ldots(x+n)}\biggr)\,\bigg\vert_{x=0}
={1\over n!}{n+1\brack2}\,.
\enddisplay

\bugonpage 270, line 8 (31 Oct 88)

We can prove Bernoulli's formula \equ(6.78) by induction on~$m$,
using the\cutpar

\bugonpage 270, bottom six lines and continuing to page 271 (28 Oct 88)

\vskip-20pt
\begindisplay \openup3pt
n^{m+1}&=\sum_{j=0}^m{m+1\choose j}S_j(n)=\sum_{j=0}^m{m+1\choose j}\widehat S_j
 (n)+{m+1\choose m}\,\Delta\cr
&=\sum_{j=0}^m{m+1\choose j}{1\over j+1}\sum_{k=0}^j{j+1\choose k}B_kn^{j+1-k}+(m+1)\,\Delta\cr
&=\sum_{0\le k\le j\le m}{m+1\choose j}{j+1\choose k}{B_k\over j+1}n^{j+1-k}+(m+1)\,\Delta\cr
&=\sum_{0\le k\le j\le m}{m+1\choose j}{j+1\choose j-k}{B_{j-k}\over j+1}n^{k+1}+(m+1)\,\Delta\cr
&=\sum_{0\le k\le j\le m}{m+1\choose j}{j+1\choose k+1}{B_{j-k}\over j+1}n^{k+1}+(m+1)\,\Delta\cr
&=\sum_{0\le k\le m}{n^{k+1}\over k+1}\sum_{k\le j\le m}{m+1\choose j}{j\choose 
k}B_{j-k}+(m+1)\,\Delta\cr
&=\sum_{0\le k\le m}{n^{k+1}\over k+1}{m+1\choose k}\!\!
 \sum_{k\le j\le m}\!\!{m{+}1{-}k\choose j-k}B_{j-k}+(m+1)\,\Delta\cr
&=\sum_{0\le k\le m}{n^{k+1}\over k+1}{m+1\choose k}\!\!
 \sum_{0\le j\le m-k}\!\!{m{+}1{-}k\choose j}B_j+(m+1)\,\Delta\cr
&=\sum_{0\le k\le m}{n^{k+1}\over k+1}{m+1\choose k}\[m-k=0]+(m+1)\,\Delta\cr
&={n^{m+1}\over m+1}{m+1\choose m}+(m+1)\,\Delta\cr
&=n^{m+1}+(m+1)\,\Delta\,,\qquad\hbox{where $\Delta=S_m(n)-\widehat S_m(n)$.}\cr
\enddisplay
(This derivation is a good review of the standard manipulations
we learned in Chapter 5.) Thus $\Delta=0$ and $S_m(n)=\widehat S_m(n)$, QED.

\bugonpage 278, bottom line of graffito (21 Oct 88)

\noindent
\g\hfill\dash---E. Lucas [207]\g

\bugonpage 279, illustration and next four lines (9 Nov 88)

\vskip-20pt
\begindisplay \advance\abovedisplayskip2pt
\unitlength=.0033333in
\beginpicture(320,320)(0,0)
\multiput(40,0)(40,0)7{\line(0,1){320}}
\multiput(0,40)(0,40)7{\line(1,0){320}}
\put(0,0){\squine(0,160,320,0,0,0)}
\put(0,0){\squine(0,0,0,0,160,320)}
\put(0,0){\squine(0,160,320,320,320,320)}
\put(0,0){\squine(320,320,320,0,160,320)}
\put(0,0){\squine(200,200,200,0,160,320)}
\put(0,0){\squine(0,100,200,200,160,120)}
\put(0,0){\squine(202,259,316,0,160,320)}
\endpicture
\hskip6em
\beginpicture(512,320)(0,-60)
\put(42,0){\line(0,1){199}}
\put(82,0){\line(0,1){199}}
\put(122,0){\line(0,1){199}}
\put(161,0){\line(0,1){199}}
\put(199,0){\line(0,1){199}}
\put(237,0){\line(0,1){199}}
\put(275,0){\line(0,1){199}}
\put(313,0){\line(0,1){199}}
\put(351,0){\line(0,1){199}}
\put(390,0){\line(0,1){199}}
\put(430,0){\line(0,1){199}}
\put(470,0){\line(0,1){199}}
\put(0,41){\line(1,0){512}}
\put(0,80){\line(1,0){512}}
\put(0,119){\line(1,0){512}}
\put(0,158){\line(1,0){512}}
\put(0,0){\squine(0,0,0,0,99.5,199)}
\put(0,0){\squine(512,512,512,0,99.5,199)}
\put(0,0){\squine(0,256,512,0,0,0)}
\put(0,0){\squine(0,256,512,199,199,199)}
\put(0,0){\squine(0,256,512,195,99.5,4)}
\put(0,0){\squine(199,199,199,0,60.5,121)}
\put(0,0){\squine(313,313,313,199,138.5,78)}
\endpicture
\enddisplay
Presto: The original area of $8\times8=64$ squares has been rearranged
to yield $5\times13=65$ squares! A similar construction dissects any
$F_n\times F_n$ square into four pieces, using $F_{n+1}$, $F_n$, $F_{n-1}$,
and~$F_{n-2}$ as dimensions wherever the illustration has
$13$, $8$, $5$, and $3$ respectively. The result is an $F_{n-1}\times
F_{n+1}$\cutpar

\bugonpage 280, lines 7 and 4 from the bottom (5 Oct 88)

An extension of these divisibility ideas was used by Yuri "Matijasevich"
in\cutpar
\vdots\par
\noindent
Matijasevich's lemma states that, if $n>2$, the Fibonacci number~$F_m$ is
a\cutpar

\bugonpage 281, line 16 (5 Oct 88)

\noindent
We have proved Matijasevich's lemma.

\bugonpage 282, lines 4 and 5 (9 Nov 88)

\noindent
holds if
we set $k_1=k$, because the inequalities $F_{k_2}\le n-F_k<F_{k-1}$
imply that $k\gg k_2$.)
Conversely, any representation of the form \equ(6.113) implies that

\bugonpage 285, bottom line (7 Nov 88)

\noindent
(This formula was first published by Leonhard "Euler" [91] in 1765,
but people forgot about it until it was rediscovered by
 Jacques "Binet" [25] in 1843.)

\bugonpage 286, line 23 (7 Nov 88)

\noindent
is almost negligible.) For example,
$F_{10}=55$ and $F_{11}=89$ are very near

\bugonpage 289, lines 4 and 5 (7 Nov 88)

\noindent
(A closed form for \equ(6.129), generalizing the "Euler"--"Binet" formula
\equ(6.123) for Fibonacci numbers, appears in \equ(5.84).)

\bugonpage 293, lines 10 and 11 (18 Nov 88)

\noindent
covered in 1976 by J.\thinspace L.
 "Davison"~[61], is an infinite
continued fraction that relates this generating function to the Fibonacci
sequence:

\bugonpage 302, line 2 (15 Sep 88)

\indent\indent$\displaystyle
\sum_{k=0}^n {1\over F_{2^k}}=3-{F_{2^n-1}\over F_{2^n}}\,,
\qquad\hbox{integer $n\ge1$}.$

\bugonpage 310, line 6 (7 Oct 88)

\unitlength=3pt
\def\Domh{\beginpicture(3,1)(-.5,0) % horizontal, stand-alone
	\put(2,0){\line(0,1){1}}
	\put(0,0){\line(0,1){1}}
	\put(0,0){\line(1,0){2}}
	\put(0,1){\line(1,0){2}}
	\endpicture}
\def\Domv{\beginpicture(2,2)(-.5,0) % vertical, stand-alone
	\put(0,0){\line(0,1){2}}
	\put(1,0){\line(0,1){2}}
	\put(0,0){\line(1,0){1}}
	\put(0,2){\line(1,0){1}}
	\endpicture}
\noindent
in the commutative version of~$T$
is $35@\Domv^4\Domh^6$.

\bugonpage 316, line 7 (6 Nov 88)

\vskip-20pt
\begindisplay \let\preamble=\tablepreamble \offinterlineskip
C_n&&1&\phantom5&\phantom{10}&\phantom{15}&\phantom{20}&\phantom{25}&
\phantom{30}&\phantom{35}&\phantom{40}&\phantom{45}&50\cr
\enddisplay

\bugonpage 316, line 8 from the bottom (6 Nov 88)

\vskip-20pt
\begindisplay \tightplus \let\displaythick=\normalthick
5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1\,;
\enddisplay

\bugonpage 317, line 5 from the bottom (31 Oct 88)

\noindent
the notation of Chapter~9, $g_n=O\bigl(\vert1/z_0\vert^n
\bigr)$ if there is convergence at~$z_0$. And\cutpar

\bugonpage 322, line 8 from the bottom (7 Nov 88)

\noindent
for $\<1,0,1,0,\ldots\,\>$ is $\half\bigl(G(z)+G(-z)\bigr)=
\half\bigl({1\over1-z}+{1\over1+z}\bigr)={1\over1-z^{2\mathstrut}}$.

\bugonpage 332, line 13 (6 Nov 88)

\vskip-20pt
\begindisplay
&{2000004\choose 4}+45{2000003\choose4}+52{2000002\choose4}+2{2000001\choose4}\cr
\enddisplay

\bugonpage 339, line 3 (14 Nov 88)

\vskip-20pt
\begindisplay
{z\over\ln(1+z)}=-\sum_{n\ge0}(-z)^n\sigma_n(n-1)
=\textstyle 1+\half z-{1\over12}z^2+\cdots\,.
\enddisplay

\bugonpage 341, line 11 (6 Nov 88)

\noindent
$r+k\choose k$ by $l+k\choose l$ and $s+n-k\choose n-k$
by $m+n-k\choose m$; then we can change $k$ to~$k-l$ and\cutpar

\bugonpage 343, line 7 from the bottom (20 Sep 88)

\noindent
Step 1 is now complete. Step 2 tells us to multiply by $z^n$ and sum:

\bugonpage 351, line 5 (14 Nov 88)

\def\chapno{7} \eqcount=72
\vskip-20pt
\begindisplay
\int_0^z@\sum_{n\ge0}g_n\,{t^n\over n!}\,dt=\sum_{n\ge0}g_n\,{z^{n+1}\over
 (n+1)!}=\sum_{n\ge1}g_{n-1}\,{z^n\over n!}\,;
\eqno
\enddisplay

\bugonpage 369, lines 17--19 (30 Oct 88)

\noindent
With fair dice ($\Pr=\Pr_{00}$), this happens with probability~$1\over6$;
with loaded dice ($\Pr=\Pr_{11}$), it happens with probability
${1\over16}+{1\over64}+{1\over64}+
{1\over64}+{1\over64}+{1\over16}={3\over16}$, the same as we observed
for doubles.

\bugonpage 369, lines 10--12 from the bottom (30 Oct 88)

\vskip-20pt
\begindisplay \let\preamble=\tablepreamble \offinterlineskip
s&&2&3&4&5&6&7&8&9&10&11&12&\kern-1em\kern1pt\cr
\noalign{\hrule}
\omit&height 1pt\cr
\Pr_{00}\[S=s]&&{1\over36}&{2\over36}&{3\over36}&{4\over36}&
 {5\over36}&{6\over36}&{5\over36}&{4\over36}&
 {3\over36}&{2\over36}&{1\over36}\cr
\omit&height 2pt\cr
\noalign{\hrule}
\Pr_{11}\[S=s]&&{4\over64}&{4\over64}&{5\over64}&{6\over64}&
 {7\over64}&{12\over64}&{7\over64}&{6\over64}&
 {5\over64}&{4\over64}&{4\over64}\cr
\enddisplay

\bugonpage 373, line 19 (28 Oct 88)

\vskip-20pt
\begindisplay
EX_1=\textstyle{99\over100}\cdot0+{1\over100}\cdot100=1\,,
\enddisplay

\bugonpage 376, line 6 from the bottom (21 Nov 88)

\noindent
time.
These are the cases $\alpha=4VX$ and $\alpha=100VX$ of Chebyshev's inequality.

\bugonpage 378, lines 7 and 8 from the bottom (21 Nov 88)

\noindent
tion $\hat\sigma=\sqrt{\hat VX}$, and presenting the answer
in the form `$\,\hat\mu\pm\hat\sigma/\mskip-1mu\sqrt n\,$'.
 For example, here are ten
rolls of two supposedly fair dice:

\bugonpage 379, top two lines (21 Nov 88)

\noindent
We estimate the average spot sum of these dice to be $7.4\pm2.1/\mskip-1mu
\sqrt{10}=7.4\pm0.7$,
on the basis of these experiments.

\bugonpage 379, line 9 (21 Nov 88)

\def\chapno{8} \eqcount=21
\vskip-20pt
\begindisplay
P(n,k)={1\over n!}{n\choose k}(n-k)\?={1\over k!}{(n-k)\?\over(n-k)!}
\eqno
\enddisplay

\bugonpage 383, line 7 (21 Nov 88)

\def\chapno{8} \eqcount=36
\vskip-20pt
\begindisplay
G_{X+Y}(z)=G_X(z)\,G_Y(z)\,,\qquad\hbox{if $X$ and $Y$ are independent}.
\eqno
\enddisplay


\bugonpage 383, line 11 from the bottom (21 Nov 88)

\vskip-20pt
\begindisplay
H''(z)&=F''(z)@G(z)+2F'(z)@G'(z)+F(z)@G''(z)\,.
\enddisplay

\bugonpage 392, line 18 (18 Nov 88)

\vskip-20pt
\begindisplay
(1-S)(1-{\tt T}-{\tt H})^{-1}\,{\tt THTTH}=S(1+{\tt TTH})\,.
\enddisplay

\bugonpage 394, first line of second graffito (10 Sep 88)

\noindent
\g Of \undertext{course} not! Who\g

\bugonpage 395, line 5 (21 Nov 88)

\vskip-20pt
\begindisplay
S_B&=\tt HTT+THTT+HTHTT+TTHTT+THTHTT+TTTHTT+\cdots\,.\cr
\enddisplay

\bugonpage 402, line 16 (21 Nov 88)

\vskip-20pt
\begindisplay \let\preamble=\tablepreamble \let\quad=\enspace
&\omit&(P_1,\ldots,P_{16})&=&1&1&1&2&1&1&1&1&2&2&3&1&2&1&3&3&.\cr
\enddisplay

\bugonpage 403, bottom three lines of graffito (21 Nov 88)

\noindent
\g say something
is ``"obvious",\qback'' ``"clear",\qback'' or ``"trivial".\qback''\g

\bugonpage 408, lines 2 and 3 from the bottom (31 Oct 88)

\vskip-20pt
\begindisplay \openup5pt
VA={VB\over n^2}&={B_n''(1)+B_n'(1)-B'_n(1)^2\over n^2}\cr
&={n(n-1)\over m^2n^2}\biggl({(n+1)(n-2)\over4}+{m\over2}-{n(n-1)\over4}\biggr)\cr
\enddisplay

\bugonpage 409, line 16 (21 Nov 88)

\vskip-20pt
\begindisplay \let\preamble=\tablepreamble \let\quad=\enspace
&\omit&(P_1,\ldots,P_{16})&=&1&1&1&2&1&1&1&1&2&2&3&1&2&1&3&3\cr
\enddisplay

\bugonpage 409, lines 9 and 10 from the bottom (1 Nov 88)

\vskip-20pt
\begindisplay
&s_1\cdt1^2+s_2\cdt1^2+s_3\cdt1^2+s_4\cdt2^2+\cdots+s_{16}\cdt3^2\cr
&\qquad-(s_1\cdt1+s_2\cdt1+s_3\cdt1+s_4\cdt2+\cdots+s_{16}\cdt3)^2\,.
\enddisplay

\bugonpage 410, line 6 (1 Nov 88)

\vskip-20pt
\begindisplay
V@A&=\sum_{1\le h_1,\ldots,h_n\le m}{1\over m^n}
 \biggl(\sum_{k=1}^n s_k P(h_1,\ldots,h_n;k)\biggr)^{\!2}
\enddisplay

\bugonpage 410, line 9 (1 Nov 88)

\vskip-20pt
\begindisplay
AV&=\sum_{1\le h_1,\ldots,h_n\le m}{1\over m^n}
 \Biggl(\sum_{k=1}^n s_k P(h_1,\ldots,h_n;k)^2
\enddisplay

\bugonpage 427, line 17 (30 Oct 88)

\noindent
but $n^\epsilon\ge 10^{10^k}$. The ratio $(\log n)/n^\epsilon$ therefore
approaches zero as $n\to\infty$.

\bugonpage 429, first line of graffito (21 Sep 88)

\noindent
\g``\dots\ wir durch das\g

\bugonpage 430, lines 14--17 (22 Oct 88)

\def\chapno{9}\eqcount=10
\noindent
one quantity (say~$n$) whose value is varying.
The formula
\begindisplay
f(n)=O\bigl(g(n)\bigr)\qquad\hbox{for all $n$}
\eqno
\enddisplay
means in this context that there is a constant $C$ such that
\begindisplay
\bigl\vert f(n)\bigr\vert\le C\bigl\vert g(n)\bigr\vert\qquad\hbox{for all $n$};
\eqno
\enddisplay

\bugonpage 435, line 9 (21 Sep 88)

\noindent pensated by the improved understanding that comes with~$O$-bounds.

\bugonpage 445, line 7 from the bottom (21 Sep 88)

\noindent
unknown $O$-constants are reasonably small.
With a pocket calculator we find\cutpar

\bugonpage 448, line 7 from the bottom (22 Sep 88)

\noindent
led "Bachmann" to invent $O$-notation in the first place.)

\bugonpage 463, line 13 (31 Oct 88)

If all were well with the world, we would be able to show that $R_4(n)$ is\cutpar

\bugonpage 464, line 4 (31 Oct 88)

\vskip-20pt
\begindisplay
\phantom{R_4(n)}
&=R_4(\infty)+O\Bigl(\int_n^\infty x^{-6}\,dx\Bigr)=R_4(\infty)+O(n^{-5})\,.
\enddisplay

\bugonpage 468, bottom line (21 Nov 88)

\vskip-20pt
\begindisplay
\phantom{\Theta_n}
&=\cdots+e^{-9/n}+e^{-4/n}+e^{-1/n}+1+e^{-1/n}+
 e^{-4/n}+e^{-9/n}+\cdots\,.
\enddisplay

\bugonpage 476, line 3 (26 Oct 88)

\hangindent\parindent\textindent{\bf10\hss}%
Prove or disprove: $O\bigl(\vert f(n)\vert^\alpha\bigr)=
 O\bigl(f(n)\bigr)^{\mskip-1mu\alpha}$ for all real $\alpha>0$.

\parindent=30pt % for the Answers
\bugonpage 489, tenth line of graffito (12 Sep 88)

\noindent
\g of thinking of what\g

\bugonpage 489, lines 13--22 (12 Oct 88)

\textindent{\bf2.21\hss}%
Extracting the final term of $S_{n+1}$ gives $S_{n+1}=1-S_n$;
extracting the first term gives
\begindisplay
S_{n+1}=(-1)^{n+1}+\sum_{1\le k\le n+1}(-1)^{n+1-k}
&=(-1)^{n+1}+\sum_{0\le k\le n}(-1)^{n-k}\cr
&=(-1)^{n+1}+S_n\,.\cr
\enddisplay
Hence $2S_n=1+(-1)^n$ and we have $S_n=\[\hbox{$n$ is even}]$.
Similarly, we find
\begindisplay
T_{n+1}=n+1-T_n=\sum_{k=0}^n(-1)^{n-k}(k+1)=T_n+S_n\,,
\enddisplay
hence $2T_n=n+1-S_n$ and we have $T_n=n+1-S_n=\half\bigl(n+
\[\hbox{$n$ is odd}]\bigr)$.
%(Using the notation of the next chapter, we can also write $T_n=\lceil n/2\rceil$.)
Finally, the same approach yields
\begindisplay
U_{n+1}=(n+1)^2-U_n&=U_n+2T_n+S_n\cr
&=U_n+n+\[\hbox{$n$ is odd}]+\[\hbox{$n$ is even}]\cr
&=U_n+n+1\,.\cr
\enddisplay
Hence $U_n$ is the triangular number $\half(n+1)n$.

\bugonpage 489, bottom two lines (27 Oct 88)

\noindent
$1/k+1/(k+1)$.)
 (b)~Let $u(x)=2x+1$ and $\Delta v(x)=
1/x(x+1)=(x-1)\_{-2}$; then
$\Delta u(x)=2$ and $v(x)=-(x-1)\_{-1}=-1/x$. The answer is $2H_n-{n\over n+1}$.

\bugonpage 490, top line (17 Oct 88)

\textindent{\bf2.24\hss}%
 Summing by parts, $\sum x\_m H_x\,\delta x=x\_{m+1}H_x/(m+1)
-x\_{m+1}/(m+1)^2+C$;\cutpar

\bugonpage 492, second line of answer 3.8 (1 Oct 88)

\noindent
$n/m+1\le\lceil n/m\rceil$,
contradicting \equ(3.5). The other proof is similar.

\bugonpage 492, second line of answer 3.9 (12 Oct 88)

\noindent
because $0\le{n\mathbin{\rm mumble}m}<m$.
The denominators of the representation are strictly increasing,
hence distinct, because $qn/(n\mathbin{\rm mumble}m)>q$.

\bugonpage 494, line 5 (1 Oct 88)

\noindent
$l>1$; it's $\sum_{0\le n\le M}\bigl(\lfloor n\log2-\log l@\rfloor
-\lfloor n\log2-\log(l+1)\rfloor\bigr)$.]

\bugonpage 495, lines 2 and 3 from the bottom (2 Nov 88)

\noindent
lines and $2n-1$ vertical lines between cells of the board, and the
circle crosses each of these lines twice. Since $r^2$ is not an integer, the
"Pythagorean theorem"\cutpar

\bugonpage 496, line 5 (2 Nov 88)

\vskip-20pt
\begindisplay
{\textstyle{1\over4}}\pi r^2-2r\le\sum_{0<k<r}\lfloor\sqrt{r^2-k^2}\rfloor\le
{\textstyle{1\over4}}\pi r^2\,,\qquad\hbox{$r=n-\half$}.
\enddisplay

\bugonpage 497, line 3 (17 Oct 88)

$\displaystyle
\qquad=\sum_{k,l,m}2^{-l}4^{-m}\[2^m\le l<2^{m+1}]\[2^l\le k<2^{l+1}]\[0\le m<n]$

\bugonpage 497, line 15 (23 Oct 88)

\noindent
be the point $\bigl(\{mx\},\{my\}\bigr)$. Divide the unit square $0\le x,y<1$
into triangular\cutpar

\bugonpage 501, line 5 (26 Oct 88)

\textindent{\bf4.10\hss}%
 $999(1-{1\over3})(1-{1\over37})=648$.

\bugonpage 503, line 6 from the bottom (19 Oct 88)

\noindent
$b^{m\lfloor n/m\rfloor}(a^{n\bmod m}-b^{n\bmod m})$.

\bugonpage 512, lines 16--17 (28 Oct 88)

\noindent
$(k+1)(k+3)/(k+2)$. (d)~No, the term ratio is
$1+1/(k+1)H_k$; and $H_k\sim \ln k$ isn't a rational function.
(e)~Yes, the term ratio is

\bugonpage 515, lines 15--16 (22 Oct 88)

\textindent{\bf5.40\hss}%
 $(-1)^{m+1}\sum_{k=1}^n\sum_{j=1}^m{r\choose j}{m-rk-s-1\choose m-j}=
(-1)^{m+1}\sum_{k=1}^n\bigl({m-r(k-1)-s-1\,\choose m}-{m-rk-s-1\choose m}\bigr)
=(-1)^{m+1}\bigl({m-s-1\choose m}-{m-rn-s-1\choose m}\bigr)=
{rn+s\choose m}-{s\choose m}$.

\bugonpage 526, lines 11--12 (4 Oct 88)

\textindent{\bf5.97\hss}The congruence surely holds if $2n+1$ is prime.
Steven Skiena has also
found the example $n=2953$, when $2n+1=3\cdt11\cdt179$.

\bugonpage 528, line 14 (30 Oct 88)

\noindent
are called
"Genocchi numbers"~$\<1,1,3,17,155,2073,\ldots\,\>$,
after Genocchi~[117].)

\bugonpage 543, line 6 (10 Nov 88)

\noindent
so $[z^n]\,\check G(z)={1\over4}\bigl(2n+3+(-1)^n\bigr)$.
Setting $n=50$ yields $26$ ways to make\cutpar

\bugonpage 548, bottom two lines (26 Oct 88)

\noindent
form in terms of other quantities that we have discussed in
\g\vskip-22pt Give me "Legendre" polynomials and I'll~give you a "closed~form".\g
this book,
but their asymptotic behavior is known [173, exercise
2.2.1--12].\par

\bugonpage 569, bottom line (19 Sep 88)

\noindent
exercise.
We have $\ln S=\gamma_1$ in the notation of answer 9.57.)

\bugonpage 572, top line (22 Nov 88)

\textindent{\bf9.42\hss}%
The hint follows since ${n\choose k-1}\big/{n\choose k}={k\over
n-k+1}\le{\alpha n\over n-\alpha n+1}<{\alpha\over1-\alpha}$. Let\cutpar

\let\,=\thinspace
\parindent=22pt \tolerance=1000 \frenchspacing % for the Bibliography
\bugonpage 579, line 13 (12 Oct 88)


Press, 1935; second edition, 1964.

\bugonpage 579, line 4 from the bottom (15 Sep 88)

fonction quand on y permute les lettres qu'elle renferme,''
{\sl Journal de}\cutpar

\bugonpage 580, top two lines (9 Nov 88)

\bib 25
J. "Binet", ``M\'emoire sur l'int\'egration des \'equations lin\'eaires
aux diff\'e\-ren\-ces finies, d'un ordre quelconque, \`a coefficients
variables,'' {\sl Comptes}\cutpar

\bugonpage 582, lines 12--13 (9 Nov 88)

\bib 57
A.\,L. "Crelle", ``D\'emonstration \'el\'ementaire du th\'eor\`eme de
"Wilson" g\'en\'e\-ralis\'e,''
{\sl Journal f\"ur die reine und angewandte Mathematik\/ \bf20} (1840),\cutpar

\bugonpage 582, bottom two lines (21 Sep 88)

\hangindent\parindent
der
Zahlen,'' {\sl Bericht \"uber die Verhandlungen der K\"oniglich-Preu\ss ische
Akademie der Wissenschaften zu Berlin\/} (1842), 93--95. Reprinted in
his {\sl Werke}, volume~1, 635--638.

\bugonpage 583, line 7 (30 Sep 88)

\bib 70
A. Conan "Doyle", ``The sign of the four; or, The problem of the Sholtos,''\cutpar

\bugonpage 585, line 19 (12 Oct 88)

{\sl tions}, volume~1. \
Wiley, 1950; second edition, 1957; third edition, 1968.

\bugonpage 585, line 8 from the bottom (13 Oct 88)

\bib 101
Pierre "Forcadel", {\sl L'arithmeticque}. \ Paris, 1557.

\bugonpage 587, bottom line (26 Oct 88)

1989. (The first printing had a different Iversonian notation.)

\bugonpage 588, line 6 (12 Oct 88)

{\sl of Algorithms}. \
Birkh\"auser, Boston, 1981; second edition, 1982.

\bugonpage 589, line 17 (14 Nov 88)

\bib 154
Charles "Hermite", {\sl Cours de M. Hermite}. \
Facult\'e des Sciences de Paris,\cutpar

\bugonpage 590, line 10 (30 Sep 88)

{\catcode`\@=\active \def@#1{{\char#1}}
\bib 166
Flavius Josephus, {\sl I@6TOPIA IO@7@1A\"IKO@7 @5O@3EMO@7 @5PO@6
P@{10}-}\cutpar}

\bugonpage 590, line 26 (12 Oct 88)

Springer, Berlin, 1922; second edition, 1924.
Reprinted by Dover, 1945.\cutpar

\bugonpage 590, bottom five lines (12 Oct 88)

{\sl damental Algorithms}. \
Addison-Wesley, 1968; second edition, 1973.

\medskip
\bib 174
Donald E. "Knuth", {\sl The Art of Computer Programming},
volume~2: {\sl Seminumerical Algorithms}. \
Addison-Wesley, 1969; second edition, 1981.

\medskip
\bib 175
Donald E. "Knuth", {\sl The Art of Computer Programming},
volume~3: {\sl Sorting and Searching}. \
Addison-Wesley, 1973; second printing, 1975.

\bugonpage 591, line 3 (24 Oct 88)

\bib177
Donald E. "Knuth", {\sl Mariages stables et leurs relations avec d'autres\cutpar}

\bugonpage 592, line 9 (13 Oct 88)

\bib 192
J.-L. de la Grange ["Lagrange"], ``Sur une nouvelle esp\`ece de calcul
 relatif\cutpar

\bugonpage 592, lines 20--21 (12 Oct 88)

\bib 196
Adrien-Marie "Legendre", {\sl Essai sur la Th\'eorie des Nombres}. \
Paris, 1798; second edition, 1808. Third edition (retitled {\sl Th\'eorie
des Nombres}, in\cutpar

\bugonpage 593, line 3 (22 Oct 88)

\bib 205
E. "Lucas", ``Sur les rapports qui existent entre la th\'eorie des nombres\cutpar

\bugonpage 593, lines 6--9 (14 Nov 88)

\bib 206
\'Edouard "Lucas", ``Sur les congruences des nombres eul\'eriens et des
coefficients diff\'erentiels des fonctions trigonom\'etriques, suivant un
module premier,''
{\sl Bulletin de la Soci\'et\'e math\'ematique de
France\/ \bf6} (1878), \hbox{49--54}.

\medskip
\bib 207
Edouard "Lucas", {\sl Th\'eorie des Nombres}, volume~1. \ % sic, no accent
Gauthier-Villars, Paris,\cutpar

\bugonpage 593, new bibliographic entry (22 Oct 88)

\bib 217
A. Moessner,
\g 605.\g
 ``Eine Bemerkung \"uber die Potenzen der nat\"urlichen Zahlen,''
{\sl Sitzungsberichte der Mathematisch\hskip1ptplus1pt-\hskip1ptplus1pt
Naturwissenschaftliche\break Klasse der
Bayerischen Akademie der Wissenschaften}, 1951, Heft~3, 29.\cutpar

\medskip\noindent
[The remaining items in the bibliography now need to be renumbered,
and so do the references to them {\sc throughout the book}. But the old
numbers are used in these errata.]

\bugonpage 595, line 6 (15 Sep 88)

{\sl M\'emoires de l'Acad\'emie Royale des Sciences de
l'Institut de France},\cutpar

\bugonpage 595, marginal note for number 237 (22 Oct 88)

\noindent\g vi, 16, 494, 602.\g

\bugonpage 595, lines 15 and 16 (21 Sep 88)

\bib 239
George "P\'olya" and Gabor "Szeg\H o", {\sl Aufgaben und Lehrs\"atze
aus der Analy\-sis}, two volumes. \ Julius Springer, Berlin, 1925; fourth edition,
1970\cutpar

\bugonpage 595, line 10 from the bottom (12 Oct 88)

\bib 244
John William "Strutt", Third Baron "Rayleigh", {\sl The Theory of Sound}. \
First edition, 1877; second edition, 1894. \ (The cited material about
irrational\cutpar

\bugonpage 596, line 2 (15 Sep 88)

trigonometrische Reihe,'' Habilitations\-schrift, G\"ottingen, 1854.
Pub-\cutpar

\bugonpage 596, lines 25--28 (21 Sep 88)

\bib 258
Ernst "Schr\"oder", ``Vier combinatorische Probleme,''
{\sl Zeitschrift f\"ur Mathe\-matik und Physik\/ \bf15} (1870), 361--376.

\medskip
\bib 259
Heinrich "Schr\"oter", ``Ableitung der Partialbruch- und Produkt-Entwicke\-lungen %sic
f\"ur die trigonometrischen Funktionen,''
{\sl Zeitschrift f\"ur Mathe-}\cutpar

\bugonpage 598, line 7 from the bottom (15 Sep 88)

Press, Oxford, 1951; second edition, revised by D.\thinspace R.
"Heath-Brown", 1986.

\bugonpage 599, line 9 (12 Oct 88)

\bib 295
Edward "Waring", {\sl Meditationes Algebra{\"\i}c\ae}.\
Cambridge, 1770; third edi-\cutpar

\bugonpage 600, bottom line (15 Sep 88)

{\sl Royale des Sciences de Li\`ege\/ \bf41}
(1972), 179--182.

\parindent=30pt % for the Credits
\bugonpage 605, first two lines (22 Oct 88)

\noindent\hbox to\parindent{\bf7.54\hfil}Moessner [217].

\bugonpage 605, left column (22 Sep 88)

\noindent\hbox to\parindent{\bf8.53\hfil}Feller [96] credits S. N. Bernstein.

\parindent=0pt % for the Index
\bugonpage 606, top line (31 Aug 88)

[delete the big `I' at the top of this page, and the extra occurrences
of~`I' in the running headlines at the top of pages 607--623]

\bugonpage 607, left column (2 Oct 88)

Baseball, 73, 148, 195, 616, 620.

\bugonpage 607, right column (5 Oct 88)

{\hsize=2.75in \hangindent=20pt
Bernshte{\u\i}n (= Bernstein), Serge{\u\i} Natanovich, 605.\par}

\bugonpage 609, top line (26 Oct 88)

Closed form, 3, 7, 108, 317, 548.

\bugonpage 609, right column (21 Sep 88)

de Branges, Louis, 589.

\bugonpage 610, right column (6 Oct 88)

Durst, Lincoln Kearney, viii.

\bugonpage 610, right column (10 Oct 88)

Egyptian mathematics, 95, 150, 581.\par
Einstein, Albert, 72, 293.

\bugonpage 612, new entry for left column (2 Oct 88)

Football, 182.

\bugonpage 612, right column (22 Sep 88)

Fre{\u\i}man, Grigori{\u\i} Abelevich, 581.

\bugonpage 612, right column (21 Sep 88)

{\hsize=2.75in \hangindent=20pt \raggedright
Gau{\ss} (= Gauss), Karl (= Carl) Friedrich, vii, 6, 7, 123, 205, 207, 212, 496, %
 514, 583, 586, 602, 603.\par}

\bugonpage 613, left column (31 Aug 88)

God, 1, 293.

\bugonpage 614, left column, line 7 (2 Nov 88)

{\hsize=2.75in \noindent\kern10pt\hangindent=30pt \raggedright
sums of, 41, 56, 265--268, 298--299, 302, 340--341.\par}

\bugonpage 614, new entry for left column (10 Oct 88)

Heath-Brown, David Rodney, 598.

\bugonpage 614, left column (15 Sep 88)

Hofstadter, Douglas Richard, 602.

\bugonpage 614, left column (12 Oct 88)

Horses, 17, 454, 489.

\bugonpage 614, right column under Iverson (26 Oct 88)

\quad convention, 24, 31, 34, 68, 75, 587.

\bugonpage 615, left column (13 Sep 88)

Kissinger, Henry Alfred, 365.

\bugonpage 615, right column (15 Sep 88)

lcm: Least common multiple, 103.
\par\vdots\par
lg: Binary logarithm, 70.
\par\vdots\par
ln: Natural logarithm, 262.

\bugonpage 615, right column (26 Oct 88)

Legendre, Adrien Marie, 548, 592, 602.

\bugonpage 616, first line (22 Oct 88)

{\hsize=2.75in \hangindent=20pt \raggedright
Lucas, Fran\c cois \'Edouard Anatole, 1, 278, 593, 602--604.\par}

\bugonpage 616, left column (5 Oct 88)

{\hsize=2.75in \hangindent=20pt
Mati{\t\i}asevich (= Matijasevich), \t{I}uri{\u\i} (= Yuri) Vladimirovich, %
 280, 593, 604.\par}

\bugonpage 616, right column (22 Oct 88)

Moessner, Alfred, 593, 605.

\bugonpage 617, right column (15 Sep 88)

[omit the entry for C.\thinspace M. Pearcy, Jr.]

\bugonpage 618, right column (2 Nov 88)

Porter, Thomas K, 601.

\bugonpage 619, left column (22 Oct 88)

Ramshaw, Lyle Harold, 73, 601, 603, 605.

\bugonpage 620, new entry for left column (4 Oct 88)

Skiena, Steven Sol, 526.

\bugonpage 620, right column (21 Sep 88)

Stanford University, v, vii, ix, 413, 625.

\bugonpage 620, right column (24 Sep 88)

Steele, Guy Lewis, Jr., 597.

\bugonpage 621, left column, line 7 (5 Oct 88)

\noindent\kern10pt
constants, 569, 575.

\bugonpage 621, right column, line 18 (2 Nov 88)

\hskip30pt 298--299, 302, 340--341.

\bugonpage 623, new entry for left column (17 Oct 88)

Whidden, Samuel Blackwell, viii.

\bye
