% Bugs (sigh) in Concrete Math

\input gkpmac
\preprintfalse
\raggedbottom
\advance\vsize10pt
\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 Math Errata VI

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 sixth printing (October 1990)
of {\sl Concrete Mathematics\/} by Graham, Knuth, and Patashnik.
The seventh printing (December 1991) 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}

\vskip.5in % reduce this if there's more before the marginal stuff

\bugonpage 14, line 17 (15 Sep 91)

\noindent
that will define it.
\kern-1ptPlugging the constant function $f(n)\kern-1pt=\kern-1pt1$ into \equ(1.11) says~that\cutpar

\bugonpage 15, line 14 of graffiti (16 Sep 91)

\noindent
\g
in the sense that the\g

\bugonpage 39, new graffito for bottom of page (15 Sep 91)

\noindent
\g \vskip-42pt Watch out---\par
the authors\par seem to think that
$j$, $k$, and $n$ are ``actual numbers.''\g\vskip-30pt

\bugonpage 41, change graffito and move to top of page (22 Nov 90)

\noindent
\g \vskip-.3in It's smart
 to say $k\le n$ instead of $k\le n-1$ here.
Simple bounds save energy.\g\vskip-30pt

\bugonpage 44, line 2 from the bottom (15 Sep 91)

\noindent
and we have already determined $A(n)$, $B(n)$, and $C(n)$, because
\equ(2.40) is the\cutpar

\bugonpage 55, line 13 from the bottom (15 Sep 91)

\noindent
Substituting $Ev(x)$ for $v(x{+}1)$ yields a compact
rule for the difference of a\cutpar

\bugonpage 60, line 16 from the bottom (15 Sep 91)

\noindent
Otherwise $\sum_{k\in K}a_k$ is undefined.
(See exercise~18.)

\bugonpage 70, lines 16--18 (15 Sep 91)

\noindent
put them to use, starting with an easy problem:
What's $\lceil@ \lg 35@ \rceil$?
(Following a suggestion of Edward~M. "Reingold",
we use `$\lg$' to denote the base-$2$ logarithm.)
Well, since $2^5 < 35 \leq 2^6$,
we can take logs to get $5 < \lg 35 \leq 6$;
so relation \equ(3.5\rm(c))~tells us
 that $\lceil @ \lg 35 @ \rceil = 6$.

\bugonpage 120, line 17 (16 Sep 91)

\noindent
$m'/n'$
enclosing~$f(S)$. We could put the $m$'s on top and the $n$'s on the
bottom,\cutpar

\bugonpage 123, lines 15--19 (12 Feb 91)

\noindent
Just as every real number~$x$ in $[@0\dts1)$ has an infinite binary
representation $(.b_1b_2b_3\ldots\,)_2$ not ending with all $1$'s,
every real number $\alpha$ in $[@0\dts\infty)$ has an infinite Stern--Brocot
representation $B_1B_2B_3\ldots$ not ending with all $R$'s. Thus we have
a one-to-one order-preserving correspondence between $[@0\dts1)$ and
$[@0\dts\infty)$ if we let $0\leftrightarrow L$ and $1\leftrightarrow R$.

\bugonpage 127, line 9 from the bottom (12 Feb 91)

\noindent
handle integers in the
range $[-2^{31}\dts2^{31})$ can easily compute sums, differences,\cutpar

\bugonpage 130, line 13 from the bottom (12 Feb 91)

\noindent
if a value $j\in[@0\dts m)$ is given,
 we can explicitly compute $k\in[@0\dts m)$
such that\cutpar

\bugonpage 136, line 3 (6 Oct 90)

\noindent that
even more is true. Hence the curious fact and its converse are both facts.

\bugonpage 136, lines 11 and 12 (6 Oct 90)

\vskip-20pt
\begindisplay \let\preamble=\tablepreamble
m&&1&2&3&4&5&6&7&8&9&10&11&12\cr
\noalign{\hrule}
\mu(m)&& 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0\cr
\enddisplay

\bugonpage 137, lines 4 and 5 (15 Sep 91)

\noindent
the curious fact we proved a minute or two ago.
 Therefore we can figure out what
$\mu(m)$ is if we compute $\mu(p^k)$.

\bugonpage 137, lines 2 and 3 from the bottom (12 Feb 91)

\noindent
series $\Fscr_n$. This is the number of reduced fractions in
$[@0\dts1]$ whose denominators do not exceed~$n$, so it is $1$~greater than
$\Phi(n)$ where we define

\bugonpage 138, line 5 from the bottom (6 Oct 90)

\vskip-20pt \def\chapno{4}\eqcount=60
\begindisplay
g(x)=\sum_{d\ge1}f(x/d)\qquad\iff\qquad
f(x)=\sum_{d\ge1}\mu(d)@g(x/d)\,.
\eqno
\enddisplay

\bugonpage 146, lines 8--10 from the bottom (12 Feb 91)

{\leftskip=\parindent
\noindent
$(.b_1b_2b_3\ldots\,)_2$ in $[@0\dts1)$ and Stern--Brocot
real numbers $\alpha=B_1B_2B_3\ldots$ in~$[@0\dts\infty)$. If $x$ corresponds
to $\alpha$ and $x\ne0$, what number corresponds to~$1-x$?
\par}

\bugonpage 148, line 20 (12 Feb 91)

$m/n\in[@0.3155\dts0.3165)$.)

\bugonpage 148, lines 5 and 6 of middle graffito (15 Sep 91)

\noindent
\g Mark, who was batting
.080, gets \g

\bugonpage 149, line 4 (26 Sep 91)

\itemitem{b} Prove that $R(N)=\sum_{d\ge 1}\lfloor N/d\rfloor^2\mu(d)$.

\bugonpage 194, line 8 (16 Sep 91)

\vskip-20pt
\begindisplay
h(n,k)={n\choose k}h(n-k,0)={n\choose k}(n-k)\?\,.
\enddisplay

\bugonpage 210, lines 5--7 from the bottom (14 Mar 91)

\noindent
to extend the definition to all complex $z$ (except negative integers).
Still another definition comes from "Stirling"'s interpolation of
$\ln z!$ in \equ(5.47). All of these approaches lead to
the same generalized factorial function.

\bugonpage 263, lines 9 and 10 from the bottom (14 Mar 91)

\noindent
If $r>1$, these numbers approach a limit as $n\to\infty$; we noted in
exercise 2.31
that this limit is conventionally called "Riemann"'s "zeta function":

\bugonpage 269, lines 3 and 4 from the bottom (16 Sep 91)

That was Bernoulli's empirical discovery. (He did not give a proof.)
In modern notation we write the coefficients
in the form

\bugonpage 353, line 9 (15 Sep 91)

\vskip-20pt
\begindisplay
\hat S(z,n)&=\hat B(z)\,{e^{nz}-1\over z}
\enddisplay

\bugonpage 359, new graffito for exercise 7.19 (15 May 91)

\noindent
\g What do you mean, ``in general''? If $f_1=f_2=\cdots=f_{m-1}=0$, the
degree of $f_n(x)$ is at most $\lfloor n/m\rfloor$.\g

\bugonpage 369, the second display (27 Oct 90)

\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}\prp(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}\prp(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 370, line 15 from the bottom (27 Oct 90)

\noindent
have $0<\Pr_{00}\prp(S=s)\cdt
\Pr_{00}\prp(P=p)\le{1\over6}\cdt{1\over9}$; this can't equal
$\Pr_{00}\prp(S=s\,{\rm and}\,P=p)$,\cutpar

\bugonpage 421, line 16 (11 Oct 90)

pairs on the front porch and $n-
[-1,0,{\rm@or\,}{+1}]$ pairs on the back porch.\cutpar

\bugonpage 437, lines 15--17 (4 Dec 90)

\noindent
and the latter sum, like $S(z)$ itself, converges absolutely for $z=z_0$
and is $O(1)$.
Table 438 lists some of the most useful asymptotic formulas,
half of which are simply based on truncation of power series according
to this rule.

\bugonpage 479, line 7 (19 Mar 91)

\hangindent\parindent \hangafter0
\vskip-20pt
\begindisplay
\sum_{k=1}^n\lfloor\log_m k\rfloor\quad\And\quad
\sum_{k=1}^n\lceil@\log_m k\rceil\,;
\enddisplay

\parindent=30pt % for the Answers

\bugonpage 502, line 6 from the bottom (12 Feb 91)

\textindent{4.30}%
The $m$ integers $x\in[A\dts A+m)$ are different mod~$m$; so their
residues\cutpar

\bugonpage 505, bottom line (12 Feb 91)

\noindent
And this is a special case of \equ(4.61) if we
set $f(x)=\[x\ge1]$.

\bugonpage 520, line 8 (11 Dec 90)

\vskip-20pt
\begindisplay
\sum_{k\le n/2}{n\choose k}=2^{n-1}+
{1\over2}{n\choose n/2}\[\hbox{$n$ is even}]\,,
\enddisplay

\bugonpage 521, line 12 (7 Mar 91)

\textindent{5.76}%
$Q_{n,k}=(n+1){n\choose k}-{n\choose k+1}$.

\bugonpage 523, line 5 from the bottom (27 Oct 90)

\vskip-20pt
\begindisplay
\prod\twoconditions{1\le i,j\le n}{i\ne j}\left(1-{z_i\over z_j}\right)^{a_i}
=\sum_{k=1}^n
 \prod\twoconditions{1\le i,j\le n}{i\ne j}\left(1-{z_i\over z_j}\right)^
  {a_i-[i=k]}.
\enddisplay

\bugonpage 527, new graffito for answer 6.8 (14 May 91)

\noindent
\g\vskip-100pt That ``true value'' is the length of 65 international miles,
but the international mile is actually only .999998 as big as
a U.\thinspace S. statute mile.\par
There are exactly 6336 kilometers in 3937 U.\thinspace S. statute
miles; the Fibonacci method converts 3937 to 6370.\g

\bugonpage 529, new graffito for answer 6.31 (15 May 91)

\noindent
\def\\{\atopwithdelims\vert\vert}%
\g${n\\k}={-k\\-n}$.\g

\bugonpage 555, line 3 from the bottom {(better spacing)} (27 Oct 90)

\noindent
$\Pr\prp(S\ge100)\le1/x^{98}(4-2x-x^2)$
for all $x\ge1$, and we get the upper bound\cutpar

\bugonpage 563, lines 4 and 5 {(better spacing)} (27 Oct 90)

\noindent
variable is $0$ or~$1$.
Let $p_0=\Pr\prp(X=Y=Z=0)$, $p_1=\Pr\prp(X=Y=\overline Z=0)$,
\dots, $p_7=\Pr\prp(\overline X=\overline Y=\overline Z=0)$,
where $\overline X=1-X$. Then $p_0+p_1+\cdots+p_7=1$, and\cutpar

\bugonpage 563, line 15 from the bottom (27 Oct 90)

\vskip-20pt
\begindisplay
\Pr\prp(X_1=x_1\ {\rm and\ \cdots\ and}\ X_n=x_n)=
\Pr\prp(X_1=x_1)\ldots\Pr\prp(X_n=x_n)\,;
\enddisplay

\bugonpage 567, new graffito to accompany answer 9.15 (6 Oct 90)

\noindent
\g (It's interesting to compare this formula with the corresponding
result for the middle \undertext{binomial} coefficient,
exercise 9.60.)\g 

\bugonpage 584, bottom three lines (25 Sep 91)

\item{}{\sl al\-ysi Finitorum ac Doctrina Serierum}. \
St.~Petersburg, Academi{\ae} Imperialis Scientiarum, 1755.
Reprinted in his {\sl Opera Omnia}, series~1, volume~10.
Translated into German, 1790.


\let\,=\thinspace \frenchspacing
\parindent=22pt \tolerance=1000 % for the Bibliography


\parindent=30pt % for the Credits


\parindent=0pt % for the Index

\bugonpage 607, under Binomial coefficients (6 Oct 90)

\quad middle, 187, 242, 481.

\bugonpage 609, left column (15 May 91)

Convolution, 197, 319, 339--350, 359.

\bugonpage 610, right column (15 Sep 91)

Dominoes, 306--313, 357, 361, 365.

\bugonpage 611, under Euler (15 Sep 91)

\quad totient function, 133--135, 137--144,\par
\qquad 150--151, 357, 448--449.

\bugonpage 616, right column (14 May 91)

Miles, 287, 296, 527.

\bugonpage 616, M\"obius entry (15 Sep 91)

\quad function, 136--139, 145, 149, 357, 448--449.

\bugonpage 616, right column (15 Sep 91)

Mu function, 136--139, 145, 149, 357, 448--449.

\bugonpage 618, second line under Phi function (15 Sep 91)

\qquad 137--144, 150--151, 357, 448--449.

\bugonpage 619, new entry for left column (12 Sep 91)

Psi function, 528.

\bugonpage 619, new entry for right column (15 Sep 91)

Reingold, Edward Martin, 70.

\bugonpage 619, right column (5 Jan 91)

Roulette wheel, 74--76, 439.

\bugonpage 620, left column (15 Sep 91)

S\'ark\"ozy, Andr\'as, 526, 597.

\bugonpage 620, new entry for right column (23 Nov 90)

Slowinski, David Allen, 109.

\bugonpage 622, left column (15 Sep 91)

Totient function, 133--135, 137--144, 150--151,\par
\qquad  357, 448--449.

\bugonpage 623, right column (11 Dec 90)

Wythoff (= Wijthoff), Willem Abraham, 586.

\bye
