% 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 Math Errata IV\kern-.1em\raise.1ex\hbox{/}V

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

Note: A ``fifth printing'' was made in July, 1990, but it unfortunately
was a hodgepodge consisting of some of the corrections below superimposed
on pages of the original printing from July, 1988. Many changes were made
between 1988 and 1990, so the resulting mixture was a mess. If you are one
of the unlucky people who possess the infamous fifth printing, you are
entitled to exchange it for a copy of the sixth.

\def\bugonpage#1(#2) \par{\bigbreak\vskip-6pt
  \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.75in % reduce this if there's more before the marginal stuff

\bugonpage 2, replacement for the existing graffito (17 Jul 90)

\noindent
\g Most of the published ``solutions'' to Lucas's problem, like the
early one of Allardice and Fraser~[7], fail to explain why
$T_n$ must be $\ge 2T_{n-1}+1$.\g

\bugonpage 6, line 7 from the bottom (29 Sep 90)

\noindent
in 1786, when he was nine years old~[73]
(see also Euler [92, part~1, \S415]):%

\bugonpage 16, lines 12 and 13 (2 May 90)

\vskip-20pt \def\chapno{1} \eqcount=16
\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

\bugonpage 20, lines 8 and 9 from the bottom (17 Jul 90)

\excount=24
\ex:
Solve infinitely many cases of the four-peg Tower of Hanoi problem
by proving that equality holds in the relation of exercise~17.

\bugonpage 33, top line (2 May 90)

\noindent
(When $x=1$, the sum is of course simply $(n+1)a$.) The right-hand side\cutpar

\bugonpage 43, line 15 (20 Aug 90)

``Well, Your Honor, we know that $\Sq_0 = 0 = 0(0+\half )(0 + 1)/3$,
so the basis\cutpar

\bugonpage 59, line 2 (2 May 90)

\noindent
since we've proved that this formula holds
when $0\le x<1$; but then we are\cutpar

\bugonpage 71, middle lines of lower graffito (28 Sep 90)

\noindent
\g was made by R.~J. "McEliece" when he\g

\bugonpage 81, lines 9 and 10 from the bottom (20 Aug 90)

\vskip-20pt \def\chapno{3} \eqcount=19
\begindisplay
\eqalign{D_0^{(q)}&=1\,;\cr
D_n^{(q)}&=\Bigl\lceil {q\over q-1}D_{n-1}^{(q)}\Bigr\rceil \,
 \qquad\hbox{for $n>0$}.\cr}
\eqno
\enddisplay

\bugonpage 81, extension to the graffito (13 Dec 89)

\noindent
\g\vskip-50pt``Known'' like, say, harmonic numbers.
A.\thinspace M. "Odlyzko" and\par
 H.\thinspace S. "Wilf" have shown that
\smallskip
$D_n^{(3)}=\lfloor({3\over2})^nC\rfloor$,
\smallskip
 where
\smallskip
$C\approx1.622270503.$\g

\bugonpage 111, line 8 of graffito (17 Jul 90)

\noindent\g$(n-2)\ldots.3\,.2\,.1$.\g

\bugonpage 185, bottom line (20 Jul 90)

\noindent
because
$(m+1)\_^{n+1}\,S_m$ is a polynomial in~$m$ of degree $\le n$.

\bugonpage 268, line 16 (20 Aug 90)

\noindent
this can readily be solved with a summation factor (exercise 5).

\bugonpage 273, line 10 (30 Sep 90)

One way to prove \equ(6.93), following an idea of B.\thinspace F. Logan,
is to consider the power series

\bugonpage 273, new graffito following {(6.94)} (30 Sep 90)

\noindent\g When $x=\tan w$, this is $\tan(z+w)$.\g

\bugonpage 286, lines 7 and 8 from the bottom (27 Sep 90)

\noindent
because $\bigl\vert\phihat^n\!/\mskip-1mu\sqrt5\,\bigr\vert<\half$ for all $n\ge0$.
When $n$ is even, $F_n$ is a little bit less than
$\phi^n\!/\mskip-1mu\sqrt5\,$; otherwise it is a little greater.


\bugonpage 287, new graffito for middle of page (17 Jul 90)

\noindent
\g The ``shift down'' rule changes $n$ to $f(n/\phi)$ and the
``shift up'' rule changes $n$ to $f(n\phi)$, where $f(x)=\lfloor x+\phi^{-1}
\rfloor$.\g

\bugonpage 291, line 8 (20 Aug 90)

\vskip-20pt \def\chapno{6} \eqcount=137
\begindisplay
\pmatrix{K_{n-2}(a_1,\ldots,a_{n-2})&
 K_{n-1}(a_1,\ldots,a_{n-2},a_{n-1})\cr
\noalign{\smallskip}
K_{n-1}(a_0,a_1,\ldots,a_{n-2})&
 K_n(a_0,a_1,\ldots,a_{n-2},a_{n-1})\cr}\,.
\eqno
\enddisplay

\bugonpage 347, line 7 from the bottom (26 Jun 90)

\noindent
some nonnegative integers $n_1$, $n_2$, \dots,~$n_m$.

\bugonpage 350, line 3 (14 Mar 90)

\noindent
which is said in \equ(5.60) to have an equally remarkable property:

\bugonpage 353, line 9 (23 Jan 90)

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

\bugonpage 353, line 5 from the bottom (26 Jun 90)

\vskip-20pt \def\chapno{7} \eqcount=77
\begindisplay
S_{m-1}(n)={1\over m}\bigl(B_m(n)-B_m(0)\bigr)\,,
\eqno
\enddisplay

\bugonpage 354, line 4 (5 Aug 90)

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

\bugonpage 377, first four lines (24 May 90)

\noindent
So Chebyshev's inequality
tells us that the final sum will lie between
\begindisplay \postdisplaypenalty=10000
\textstyle 7n-10\sqrt{{35\over6}n}\And
7n+10\sqrt{{35\over6}n}
\enddisplay
in at least 99\% of all experiments when $n$ fair dice are rolled.
For example, the odds are better
than 99 to~1 that the total value of a million rolls
will be between 6.976~million and 7.024~million.

\bugonpage 377, new graffito for the margin (24 May 90)

\noindent\g(That is, the average will fall between the stated limits
in at least 99\% of all cases when we look at a set of $n$ independent
samples, for any fixed value of $n$. Don't misunderstand
this as a statement about the
averages of an infinite sequence $X_1$, $X_2$, $X_3$, \dots\ as~$n$ varies.)\g

\bugonpage 409, line 18 (20 Aug 90)

\vskip-20pt
\begindisplay
G(3,1,4,1,\ldots,3)
&=\sum_{k=1}^{16} s_kz^{P(3,1,4,1,\ldots,3;k)}\cr
\enddisplay


\bugonpage 411, bottom line (27 Apr 90)

\vskip-20pt
\begindisplay
G_T(z)={1\over m^{n+1}}\sum_{h_1=1}^m\!
 \cdots\!\sum_{h_n=1}^m\sum_{h_{n+1}=1}^m\!z^{\alpha+\beta P(h_1,\ldots,
 h_n;h_{n+1})+\delta[P(h_1,\ldots,h_n;h_{n+1})=0]}
\enddisplay

\bugonpage 412, line 9 (27 Apr 90)

\vskip-20pt
\begindisplay
G_T(z)&=\sum_{p\ge0}\Pr\prp(P=p)z^{\alpha+\beta p+\delta[p=0]}\cr
\enddisplay

\bugonpage 424, line 14 (26 Jun 90)

\excount=59
\ex:
Use the result of the previous exercise to prove \equ(8.103).

\bugonpage 431, line 6 from the bottom (26 Jun 90)

\noindent
because it can be proved that $\vert\ln z-z+1\vert\le\vert z-1\vert^2$
when $\vert z-1\vert\le\half$.

\bugonpage 455, line 3 (26 Jun 90)

\vskip-20pt
\begindisplay
\Sigma_a(n)=\sum_{k\ge\lfloor\lg n\rfloor}a_k(n)
<\sum_{k\ge\lfloor\lg n\rfloor}{k+\ln n\over k!}\,,
\enddisplay

\bugonpage 461, line 4 from the bottom (2 May 90)

\noindent
The graph of $B_{2m+1}\bigl(\{x\}\bigr)$ looks like
$(-1)^{m+1}$ times a sine wave, so it is geo-\cutpar

\bugonpage 467, lines 8--10 from the bottom (2 May 90)

\noindent
of both sides. (The value of $e^\sigma$ turns out to
be~$\sqrt{2\pi}$, but we aren't quite ready to derive that formula. In fact,
"Stirling" didn't discover the closed form for~$\sigma$ until
several years after "de Moivre"~[64] had proved that the
constant exists.)

\bugonpage 470, line 8 (26 Jun 90)

\vskip-20pt
\begindisplay
g^{(k)}(x)=P_k(x)e^{-x^2}\,,\qquad\hbox{where
   $P_k$ is a polynomial of degree $k$}.
\enddisplay

\bugonpage 477, line 7 from the bottom (30 Jan 90)

\item{33}%
Evaluate $\sum_{k\ge0}{n\choose k}/n\_^k$ with absolute error $O(n^{-3})$.

\parindent=30pt % for the Answers

\bugonpage 484, new graffito for answer 1.6 (23 Jan 90)

\noindent
\g This answer assumes that $n>0$.\g

\bugonpage 486, last line of graffito (20 Aug 90)

\noindent
\g The Netherlands).\g

\bugonpage 502, line 8 (23 Feb 90)

\noindent
the sequence that transfers $m+1$ disks in $T_m+1+T_m$ steps.

\bugonpage 508, bottom line (8 May 90)

\noindent$m'n'')
\ge n'+\hat n>N$, a contradiction.

\bugonpage 510, lines 18--22 (29 Sep 90)

\textindent{4.66}%
\g\vskip-20pt
``No square less than $25\times10^{14}$ divides a Euclid number.''\par
\hfill---Ilan "Vardi"\g
 It is known that no square less than $36\times10^{18}$ divides
a Mersenne number or Fermat number.
But there has still been no proof of "Schinzel"'s
conjecture that there exist infinitely many squarefree Mersenne numbers.
It is not even known if there are infinitely many~$p$ such that
$p\edivides(a\pm b)$, where all prime factors of $a$ and~$b$ are~$\le31$.

\bugonpage 526, lines 9--10 (29 Sep 90)

\textindent{5.96}%
 All large $n$ have the stated property, according to S\'ark\"ozy [256$'@$].
Paul "Erd\H os" conjectures that, in fact,
$\max_p \epsilon_p\bigl({2n\choose n}\bigr)$ tends to infinity as $n\to\infty$.

\bugonpage 526, marginal note for exercise 5.97 (2 May 90)

\noindent\g \vskip-1.25in
Ilan "Vardi" notes that the condition holds for
$2n+1=p^2$, where~$p$ is prime, if~and only~if\smallskip
$2^{p-1}\bmod{p^2}=1$.\smallskip
This yields two more examples:\smallskip
$n=(1093^2-1)/2$;\par
$n=(3511^2-1)/2$.\g

\bugonpage 537, new graffito for end of exercise 6.78 (17 Jul 90)

\noindent
\g \advance\baselineskip2pt
 Exercise: $m\circ n=$\par
 \quad $mn+{}$\par
 \quad$\bigl\lfloor(m{+}1)/\phi\bigr\rfloor@n+{}$\par
 \quad$m@\bigl\lfloor(n{+}1)/\phi\bigr\rfloor$.\g

\bugonpage 543, line 3 from the bottom (26 Jun 90)

\noindent
This formula relates to the problem of $3\times n$ domino tilings; we have
$a_n=$\cutpar

\bugonpage 547, lines 9 and 10 (26 Jun 90)

\noindent
$n$ as a product of two relatively prime factors. If $n$~is
divisible by~$t$ distinct primes, $r(n)=2^t$. Hence $r(n)/n^2$ is
multiplicative and the sum is

\bugonpage 552, line 8 (26 Jun 90)

\textindent{8.14}%
 $\Mean(H)=p\Mean(F)+q\Mean(G)$;
$\Var(H)=p\Var(F)+q\Var(G)+{}$\cutpar

\bugonpage 559, line 6 (26 Jun 90)

\noindent
hence $G_n'(1)=\alpha n+\beta\bigl(1-(q_f-p_h)^n\bigr)$. (Similarly
$G_n''(1)=\alpha^2 n^2+O(n)$, so\cutpar

\bugonpage 570, lines 8 and 9 from the bottom (30 Jan 90)

\textindent{9.33}%
 We have $n\_k/n\_^k=1-k(k-1)n^{-1}+\half k^2(k-1)^2n^{-2}+O(k^6n^{-3})$;
dividing by $k!$ and summing over~$k\ge0$ yields
$e-en^{-1}+{7\over2}en^{-2}+O(n^{-3})$.

\bugonpage 571, line 7 from the bottom (26 Jun 90)

\noindent
hence the sum is $\half H_n^m+O(1)$. In general the answer is
$\half(-1)^nH_n^m+O(1)$.

\bugonpage 574, line 13 (26 Jun 90)

\textindent{9.50}%
 (a) The expected return is $\sum_{1\le k\le N}k/(k^2H_N^{(2)})
=H_N/H_N^{(2)}$, and we\cutpar

\bugonpage 576, line 1 (26 Jun 90)

\textindent{9.58}%
 Let $0\le\theta\le1$ and $f(z)=e^{2\pi iz\theta}\!/(e^{2\pi iz}-1)$.
We have

\bugonpage 577, line 11 from the bottom (29 Sep 90)

\noindent
"Euler" knew ([85$'@$] and [88, part~2, \S92]).
Integrating again yields the desired\cutpar

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

\bugonpage 578, marginal note for reference 5 (17 Jul 90)

\noindent\g 8.\g

\bugonpage 580, second line of number 29 (17 Jul 90)

{\sl Annali di Matematica pura ed applicata}, series 2, {\bf4} (1871), 338--353.

\bugonpage 584, second line of number 79 (4 Jun 90)

sums,''
{\sl Discrete Mathematics}, to appear.

\bugonpage 585, marginal note for reference 92 (29 Sep 90)

\noindent\g 6, 604.\g

\bugonpage 585, last two lines of reference 92 (29 Sep 90)

\indent\hangindent\the\parindent\hangafter1
Translated into Russian, 1768;
Dutch, 1773; French, 1774; Latin, 1790; English, 1797.

\bugonpage 588, second line of number 134 (2 May 90)

{\sl of Algorithms}. \
Birkh\"auser, Boston, 1981; third edition, 1990.

\bugonpage 589, second line of number 155 (17 Jul 90)

{\sl Matematica pura ed applicata}, series 3, {\bf5}
(1901), 57--60. Reprinted in\cutpar

\bugonpage 590, better kerning of Greek (17 Jul 90)

\begingroup
\catcode`\@=\active \def@#1{{\char#1}}
\def\spacefix#1{\kern#1.5pt} \catcode`\#=\active \let #=\spacefix
\bib 166
Flavius "Josephus", {\sl I@6TOPIA IO#-@7#-#-@1#-A\"IKO#-@7#-\ @5O@3EMO#-@7#-\
 @5PO@6 P@{10}\-MAI#+O#-@7#-@6}. \
English translation, {\sl History of the Jewish War against the}\cutpar
\endgroup

\bugonpage 591, second line of number 184 (2 May 90)

{\sl Mathematics  Magazine\/ \bf63} (1990), 21--25.

\bugonpage 591, a more correct rendition of Kramp's title page (17 Jul 90)

\bib 186
C. "Kramp", {\sl \'El\'emens d'arithm\'etique universelle}. \
Cologne, 1808.

\bugonpage 593, replacements for number 202 (30 Sep 90)

\bib{201$\kern-1pt'$}
Elliott H. "Lieb", ``Residual entropy of square ice,'' 
\g605.\g
{\sl Physical Review\/ \bf162} (1967), 162--172.

\medskip
\bib{202}
B. F. Logan,
\g602.\g
 ``The recovery of orthogonal polynomials from a sum of squares,''
{\sl SIAM Journal on Mathematical Analysis\/ \bf21} (1990), 1031--1050.

\medskip
\bib{202$\kern-1pt'$}
B. F. Logan,
\g604.\g ``Polynomials related to the Stirling numbers,'' AT\&T Bell
Laboratories technical memorandum, August 10, 1987.

\bugonpage 596, new entry (29 Sep 90)

\bib{256$\kern-1pt'$}
\g526.\g
A. S\'ark\"ozy, ``On divisors of binomial coefficients, I,''
{\sl Journal of Number Theory\/ \bf20} (1985), 70--80.

\bugonpage 600, new entry (2 May 90)

\bib{304$\kern-1pt'$}
\g603.\g
Herbert S. "Wilf", {\sl generatingfunctionology.} \ Academic Press, 1990.

\parindent=30pt % for the Credits

\bugonpage 602, left column (17 Jul 90)

\noindent[delete the entry for exercise 1.4, which was not really
suggested by Ahrens.]

\bugonpage 602, right column (30 Sep 90)

\textindent{4.56}Logan [202, eq.~(6.15)].

\bugonpage 603, right column (2 May 90)

\textindent{5.71}H.\thinspace S. Wilf [304$@'$, exercise 4.16].

\bugonpage 604, left column (30 Sep 90)

\textindent{6.66}Logan [202$'@$].

\bugonpage 604, left column (30 Sep 90)

\textindent{6.70}Euler [88, part 2, chapter 8].

\bugonpage 604, left column (30 Sep 90)

\textindent{6.74}Logan [202$'@$].

\bugonpage 604, right column (29 Sep 90)

\textindent{7.37}Euler [87, \S50]; 1971 final exam.

\bugonpage 604, second line of number 7.53 (29 Sep 90)

\S91].

\bugonpage 605, right column (30 Sep 90)

\textindent{9.66}Lieb [201$'@$]; Stanley [275, exercise\hfill\break
\null\indent 4.37(c)].

\parindent=0pt % for the Index

\bugonpage 607, under Bernoulli numbers (2 May 90)

\quad generating function for, 271, 337, 351.

\bugonpage 611, left column (29 Sep 90)

\noindent [Add `6,' to the main entry for Euler.]

\bugonpage 613, under Generating functions (2 May 90)

\quad for Bernoulli numbers, 271, 337, 351.

\bugonpage 614, left column (17 Jul 90)

Heath-Brown, David Rodney, 599.

\bugonpage 616, left column (30 Sep 90)

Logan, Benjamin Franklin (= Tex), Jr., 273,\hfill\break
\null\qquad 593, 602--604.

\bugonpage 617, right column (13 Dec 89)

Odlyzko, Andrew Michael, 81, 540, 588, 605.

\bugonpage 618, left column (2 May 90)

Phi (= Golden ratio), 70, 97, 285--287, 296, 530.

\bugonpage 619, right column (23 Feb 90)

Rolletschek, Heinrich Franz, 499.

\bugonpage 620, left column (29 Sep 90)

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

\bugonpage 623, left column (29 Sep 90)

Vardi, Ilan, 510, 526, 577, 602, 605.

\bugonpage 623, left column (2 May 90)

Wilf, Herbert Saul, 81, 500, 600, 603.

\bye
