% 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 III

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

\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 12, lines 15--22 (22 Nov 89)

\noindent
eventually reach a ``"fixed point",\qback''
where $J(n)=n$. The cyclic shift property makes it easy
to see what that fixed point
will be: Iterating the function enough times
will always produce a pattern of all $1$'s
whose value is $2^{\nu(n)}-1$,
where $\nu(n)$ is the number of $1$~bits
"!sideways addition" "!nu function"
in the binary representation of~$n$.
Thus, since $\nu(13) = 3$, we have
\begindisplay
 \overbrace{J(J( \ldots J}^
  {\hbox to0pt{\hss
   \the\scriptfont0$\scriptstyle 2$ or more $\scriptstyle J$'s\hss}}
 (13)\ldots\, )) \,=\, 2^3 - 1 \,=\, 7 \,;
\enddisplay
similarly
\begindisplay
 \overbrace{J(J( \ldots J}^
  {\hbox to0pt{\hss\the\scriptfont0$\hss\scriptstyle 8$ or more\hss}}
 ((101101101101011)_2) \ldots\, )) = 2^{10} - 1 = 1023 \,.
\enddisplay

\bugonpage 17, line 9 (17 Jun 89)

\item{}%
$n-1$, can't change color
when they're in different groups;
these are\cutpar

\bugonpage 18, bottom six lines (25 Jul 89)

\itemitem{}order of
all the equal-size disks in the final arrangement? [\Hint: This is
difficult---it's really a ``bonus problem.'']
\smallskip
\item{12}Let's generalize exercise 11a even further,
by assuming that there are $n$
different sizes of disks and exactly $m_k$ disks of size~$k$.
 Determine $A(m_1,\ldots,m_n)$, the minimum number of moves needed to transfer
a tower when equal-size disks are considered to be indistinguishable.

\bugonpage 20, lines 2 and 3 from the bottom (17 Jun 89)

\item{}%
$2^9$ possible subsets are non-Josephus, namely
$\{1,2,5,8,9\}$, $\{2,3,4,5,8\}$, and $\{2,5,6,7,8\}$. There are 13
non-Josephus sets when $n=12$, none for\cutpar

\bugonpage 55, line 7 from the bottom (16 May 89)

\vskip-20pt \def\chapno{2} \eqcount=55
\begindisplay
\sum u\,\Delta v
	= uv - \sum Ev\,\Delta u\,.
\eqno
\enddisplay

\bugonpage 61, line 4 from the bottom (17 Jun 89)

\noindent
finite subsets $G\subseteq J$. Suppose that $G$ is a finite subset
of~$J$ with $\sum_{j\in G}A_j=$\cutpar

\bugonpage 65, line 9 (7 Jun 89)

\item{29}%
Evaluate the sum $\sum_{k=1}^n (-1)^{k} k / (4k^2 - 1)$.

\bugonpage 65, line 6 from the bottom (25 Jul 89)

\item{}for all real $x\ge0$, and evaluate the sums in closed form.

\bugonpage 68, margin, last four lines of graffito (16 May 89)

\noindent \g By Iverson's bracket
 convention, this is a complete equation.\g

\bugonpage 73, lines 15--20 (30 Nov 89)

\noindent
C.\thinspace A.\thinspace R. "Hoare" and
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"}.

\bugonpage 77, line 2 from the bottom (17 Jun 89)

\vskip-20pt
\begindisplay
\phantom{N(\alpha,n)}
=\sum_k\bigi[@0<k<(n+1)/\alpha@\bigr]
\enddisplay

\bugonpage 96, line 7 from the bottom (14 May 89)

\item{18}
Prove that the boundary-value error term $S$ in \equ(3.30) is
at most $\alpha^{-1}v$.

\bugonpage 98, line 12 (25 Jul 89)

\itemitem{b}Find a function $f(n,k)$ such that exactly $\sum_{k=1}^{n-1}f(n,k)$
cells of the board lie entirely within the circle.

\bugonpage 100, lines 5--7 from the bottom (10 Oct 89)

\itemitem{b}$f(x)=[x+c$ is an integer$]$.
\smallskip
\itemitem{c}$f(x)=\max\bigl(\lfloor x\rfloor,c\bigr)$.
\smallskip
\itemitem{d}$f(x)=x+c\lfloor x\rfloor-\half[x$ is not an integer$]$.

\bugonpage 106, bottom five lines (29 Sep 89)

\noindent
the right-hand side, $q_2\ldots q_k$.
Thus $q_2\ldots q_k/p_1$ is an integer, and $q_2\ldots q_k$ has a prime
factorization in which $p_1$ appears. But $q_2\ldots q_k<n$, so it has a
unique factorization (by induction).
This contradiction shows that $p_1$ must be equal to~$q_1$ after all.
Therefore we can divide both of $n$'s factorizations by $p_1$, obtaining
$p_2\ldots p_m=q_2\ldots q_k<n$. The other factors must likewise be equal
(by induction), so our proof of uniqueness is complete.

\bugonpage 108, lines 9--11 (18 Nov 89)

\vskip-20pt \def\chapno{4} \eqcount=15
\begindisplay
e_n&=e_1e_2\ldots e_{n-1}\,+\,1\,,\qquad\hbox{when $n\ge1$}.
\eqno
\enddisplay
The sequence starts out
\begindisplay
e_1&=1+1=2\,;\cr
\enddisplay

\bugonpage 108, second line from the bottom (18 Nov 89)

\noindent
by removing the three dots:
If $n>1$ we have

\bugonpage 109, bottom two lines (14 May 89)

\noindent$2^{km}-1$ has $2^m-1$ as a factor:
\begindisplay
2^{km}-1=(2^m-1)(2^{m(k-1)}+2^{m(k-2)}+\cdots+1)\,.
\enddisplay

\bugonpage 109, line 14 (18 Nov 89)

\noindent
David Slowinski, they discovered the
largest prime known at that time,

\bugonpage 123, lines 6--10 of marginal quote (17 Nov 89)

\noindent
\g \vskip-4\baselineskip
ubi opus erit in clausulis adiungentes,
$-16\=9\break ({\rm mod.\,}5)$,
$-7\=\break15\ ({\rm mod.\,}11)$.''\g

\bugonpage 125, line 7 from the bottom (16 May 89)

\vskip-20pt \def\chapno{4} \eqcount=38
\begindisplay
\quad\iff a\=b\quad\Bigl({\rm mod}\,\,{m\over\gcd(d,m)}\Bigr)\,,
	\quad\hbox{integers $a,b,d,m$}.
\eqno
\enddisplay

\bugonpage 126, line 7 from the top (16 May 89)

\vskip-20pt \def\chapno{4} \eqcount=40
\begindisplay
\qquad\iff\hbox{$a\=b$ $\bigl($mod $\lcm(m,n)\bigr)$}\,,
	\qquad\hbox{integers $m,n>0$}.
\eqno
\enddisplay

\bugonpage 133, second line of marginal quote (17 Nov 89)

\noindent\g
numerus primus\g

\bugonpage 163, line 12 from the bottom (30 Nov 89)

\noindent
can use Taylor series and the theory of complex variables:

\bugonpage 163, line 6 from the bottom (18 Nov 89)

\noindent
does, because ${r\choose k}=O(k^{-1-r})$ by
equation \equ(5.83) below.

\bugonpage 210, lines 21--23 (22 Nov 89)

\noindent
(See exercise 21.
"Euler" [81] discovered this when he was 22 years old.)
The limit can be
shown to exist for all complex~$z$, and it is zero only when $z$~is
a negative integer. Another significant definition is

\bugonpage 212, insert a comment in the margin (31 Oct 89)

\noindent
\g A few weeks ago, we were studying what Gauss had done in kindergarten.\par
Now we're studying stuff beyond his Ph.D. thesis.\par Is~this intimidating
or what?\g

\bugonpage 217, line 2 (14 May 89)

\vskip-20pt \def\chapno{5} \eqcount=99
\begindisplay
{n\choose m}\hyp{1,\,-m}{n-m+1\,}{-1\,}\,,\qquad\hbox{integers $n\ge m\ge0$};
\eqno
\enddisplay

\bugonpage 221, new marginal comment at bottom (30 Nov 89)

\noindent
\g The function\par
$F(z)=(1-z)^r$\par
satisfies\par
$\vartheta F=z(\vartheta-r)F$.\par\vskip1.5pt
This gives another proof of the binomial theorem.\g

\bugonpage 230, lines 1--3 (7 Sep 89)

\noindent \def\chapno{5} \eqcount=129
valid for all $n\ne-1$. The shifted version of \equ(5.125) is
\begindisplay \openup4pt
&\sum\hypk_k{l+2,\,1}{l+1}z\,\delta k\cr
&\qquad ={-1\over1-z}\,{l+1/(1-z)\over l+1}\,
 \hypk_k{l+1+1/(1-z),1}{l+1/(1-z)}z\,.
\eqno
\enddisplay

\bugonpage 239, lines 3--9 get a new exercise (22 Nov 89)

\excount=77
\ex:
Assuming that $m$ is a positive integer, find a closed form for
\begindisplay
\sum_{k=0}^{2m^2}{k\bmod m\choose(2k+1)\bmod(2m+1)}\,.
\enddisplay

\ex:
\hangindent2\parindent \textindent{a}% \item combined with \itemitem
What is the greatest common divisor of ${2n\choose 1}$, $2n\choose 3$,
\dots,~$2n\choose 2n-1$? \Hint: Consider the sum of these $n$ numbers.
\itemitem{b}%
Show that the least common multiple of $n\choose0$, $n\choose1$,
\dots,~$n\choose n$ is equal to $L(n+1)/(n+1)$, where
$L(n)=\lcm(1,2,\ldots,n)$.

\ex:
Prove that ${n\choose k}\le(en/k)^k$ for all integers $k,n\ge0$.

\bugonpage 242, line 2 (25 Oct 89)

efficient~$2n\choose n$.
According to exercise 36,
the odd primes~$p$ that do {\it not\/}\cutpar

\bugonpage 276, line 1 (7 Sep 89)

One thing we can do is replace $m\brace j$ by
${m+1\brace j+1}-(j+1){m\brace j+1}$.
The $(j+1)$\cutpar

\bugonpage 296, line 8 from the bottom (17 Jun 89)

\item{}
$(z^2D^2+zD)f(z)$. Similarly it can be shown that
$\vartheta^3=z^3D^3+3z^2D^2+zD$.\cutpar

\bugonpage 317, line 16 (16 May 89)

\noindent
we might have a closed form for $g_n$, expressed in terms of~$n$.
For example, the\cutpar

\bugonpage 348, lines 17--19 (17 Nov 89)

"Raney" proved a generalization of his lemma that tells us how to count such
sequences: {\sl If\/ $\<x_1,x_2,\ldots,x_m\>$ is any sequence of integers
with $x_j\le1$ for all\/~$j$, and with $x_1+x_2+\cdots+x_m=l>0$,
then exactly $l$ of the cyclic shifts}

\bugonpage 349, line 4 from the bottom (7 Sep 89)

\vskip-20pt
\begindisplay
\Bscr_t(z)^r\!=\!e^{r\ln \Bscr_t(z)}\!=\!
\sum_{n\ge0}\!{\bigl(r\ln\Bscr_t(z)\bigr)^{\!n}
\over n!}\!=\!\sum_{n\ge0}{r^n\over n!}\biggl(-\sum_{m\ge1}
 {\bigl(1{-}\Bscr_t(z)\bigr)^{\!m}\over m}\biggr)^{\!n}
\enddisplay

\bugonpage 353, bottom line (5 Dec 89)

\noindent
sequence $\<B_0,B_1,B_2,\ldots\,\>$
with $\<1,x,x^2,\ldots\,\>$; hence the exponential generating\cutpar

\bugonpage 355, line 7 (7 Sep 89)

\vskip-20pt
\begindisplay
\textstyle t_4=3t_3+\half\bigl({3\choose1,2}2t_1t_2+{3\choose2,1}2t_2t_1\bigr)
+{1\over6}\bigl({3\choose1,1,1}t_1^3\bigr)=3t_3+6t_2t_1+t_1^3\,.
\enddisplay

\bugonpage 379, line 11 from the bottom (26 Jun 89)

\vskip-20pt
\begindisplay
F_{n,k}(\pi)&=[@\hbox{position $k$ of $\pi$ is a fixed point}]\,,
\qquad\hbox{for $\pi\in\Pi_n$}.
\enddisplay

\bugonpage 382, line 15 (28 Sep 89)

\vskip-20pt
\begindisplay
\phantom{U_n(1+t)}
&={1\over n}{n\choose1}
 +{1\over n}{n\choose2}t
 +{1\over n}{n\choose3}t^2+\cdots
 +{1\over n}{n\choose n}t^{n-1}\,.
\enddisplay

\bugonpage 395, second line from bottom (7 Sep 89)

\vskip-20pt
\begindisplay
&NB&=S_A\!\!\sum_{k=1}^{\min(l,m)}B^{(m-k)}\,\[A^{(k)}=B_{(k)}]
 \;+\;S_B\sum_{k=1}^m B^{(m-k)}\,\[B^{(k)}=B_{(k)}]\,.\cr
\enddisplay

\bugonpage 405, lines 9 and 10 (7 Sep 89)

\noindent
$\half n(n+1)/H_n-n^2\!/H_n^2$. The average number of probes
for $m=n/\!@\ln n$ as $n\to\infty$ is approximately~$2$, with standard
deviation asymptotic to $\sqrt{\mskip2mu\ln n}/\sqrt2$.

\bugonpage 408, line 14 (7 Sep 89)

\vskip-20pt
\begindisplay
\sum_{n\ge0}B_n''(1){m^n@w^n\over n!}
&=m(m{-}1)e^{w(m-2)}\bigl(\textstyle\half w^2e^w\bigr)^{\!2}
 {+}me^{w(m-1)}\bigl(\textstyle{1\over4}w^4{+}w^3\bigr)e^w\cr
\enddisplay

\bugonpage 412, bottom line (7 Sep 89)

\vskip-20pt
\begindisplay
\phantom{\Mean}\llap{Var}
(G_T)&=\beta^2\ln n-\bigl((\beta\ln n)^2+2\beta\delta\ln n-\delta^2\bigr)/n
 +O\bigl((\log n)^3\!/n^2\bigr)\,.
\enddisplay

\bugonpage 414, lines 4--8 (30 Nov 89)

\excount=11
\ex:
\hangindent2\parindent \textindent{a}% \item combined with \itemitem
If $P(z)$ is the pgf for the random variable $X$, prove that
\begindisplay
\Pr(\hbox{$X\le r$})&\le x^{-r}P(x)\qquad\hbox{for $0<x\le1$;}\cr
\Pr(\hbox{$X\ge r$})&\le x^{-r}P(x)\qquad\hbox{for $x\ge1$.}\cr
\enddisplay
(These important relations are called the {\sl "tail inequalities".})
\itemitem{b}In the special case $P(z)=(1+z)^n/2^n$, use the first tail
inequality to prove that $\sum_{k\le\alpha n}{n\choose k}\le1/\alpha^{\alpha n}
(1-\alpha)^{(1-\alpha)n}$ when $0<\alpha<\half$.

\bugonpage 416, lines 22 and 23 (30 Nov 89)

\itemitem{b}Let $p$ be the probability that the number of days is $100$ or more.
What does "Chebyshev's inequality" say about $p$?
\itemitem{c}What do the "tail inequalities" (exercise 12) tell us
about $p$?

\bugonpage 418, line 11 from the bottom (26 Jun 89)

\item{43}Find a closed form for the pgf\/ $G_n(z)=\sum_{k\ge0}p_{k,n}z^k$, where
$p_{k,n}$ is the\cutpar

\bugonpage 419, top line (1 Aug 89)

is second best, \dots,~$x_{2^n}$~is worst. When $x_j$ plays $x_k$
and $j<k$, the winner\cutpar

\bugonpage 419, line 17 (16 Nov 89)

\itemitem{}greater than the probability that $x_{j+1}$ wins,
for $1\le j<2^n$.

\bugonpage 432, lines 7 and 8 of marginal quotation (16 May 89)

\noindent
\g
paire of paralleles,
or Gemowe lines of\g

\bugonpage 434, line 4 of marginal comment (17 Aug 89)

\noindent
\g$O$\kern-1pt-notation must\g

\bugonpage 436, line 13 of lower marginal note (4 Nov 89)

\noindent
\g$S$~is a set, the no-\g

\bugonpage 446, line 11 (16 Nov 89)

\noindent
Therefore we expect $S_n$ to be about $C(\log n)^2$, for some constant~$C$.

\bugonpage 453, top three lines (5 Jul 89)

\def\chapno{9} \eqcount=62
\item{\bf3}Now prove that each of the following three sums is small:
\begindisplay \openup-2pt
&\Sigma_a(n)=\sum_{k\in T_n}a_k(n)\,;\qquad
\Sigma_b(n)=\sum_{k\in T_n}b_k(n)\,;\cr
&\hskip3em\Sigma_c(n)=\sum_{k\in D_n}\bigl\vert c_k(n)\bigr\vert\,.
\eqno
\enddisplay

\bugonpage 467, lines 8 and 9 from the bottom (16 Nov 89)

\noindent
that until later. In fact,
"Stirling" discovered a closed form for
this constant only after "de Moivre"~[64]
had proved its existence.)

\bugonpage 470, line 14 (7 Sep 89)

\vskip-20pt
\begindisplay
\sum_{k=1}^m {B_k\over k!}f^{(k-1)}(x)\big\vert_{-\infty}^{+\infty}
\enddisplay

\bugonpage 472, lines 14 and 15 (6 Dec 89)

\noindent
Things are looking reasonably good, since we know how to approximate
${(n\pm k)}!$ when $n$ is large and $k$ is small.

\parindent=30pt % for the Answers

\bugonpage 484, bottom 11 lines (25 Jul 89)

(b) Let $B_n$ be the minimum number of moves. Then $B_1=3$, and it can be
shown that no strategy does better than $B_n=A_{n-1}+2+A_{n-1}+2+B_{n-1}$
when $n>1$. Hence $B_n=2^{n+2}-5$, for all $n>0$.
Curiously this is just~$2A_n-1$, and we also have
$B_n=A_{n-1}+1+A_{n-1}+1+A_{n-1}+1+A_{n-1}$.
\smallskip
\textindent{1.12}%
 If all $m_k>0$, then $A(m_1,\ldots,m_n)=2A(m_1,\ldots,m_{n-1})+m_n$.
This is an equation of the ``generalized Josephus'' type, with solution
$(m_1\ldots m_n)_2=2^{n-1}m_1+\cdots+2m_{n-1}+m_n$.

 Incidentally, the
corresponding generalization of exercise 11b
appears to satisfy the recurrence
\begindisplay
B(m_1,\ldots,m_n)=\cases{A(m_1,\ldots,m_n),&if $m_n=1$;\cr
\noalign{\vskip2pt}
  2m_n-1,&if $n=1$;\cr
\noalign{\vskip2pt}
  2A(m_1,\ldots,m_{n-1})+2m_n\!\!\cr
   \quad{}+B(m_1,\ldots,m_{n-1}),&if $n>1$ and $m_n>1$.\cr}
\enddisplay

\bugonpage 490, line 3 from the bottom (7 Jun 89)

\noindent
neighbors. Hence the answer is $-1/4+(-1)^n/(8n+4)$.

\bugonpage 492, insert new material after line 10 (16 Nov 89)

\noindent
Colin "Mallows" observes that the sequence can also be defined by the recurrence
\begindisplay
f(1)=1\,;\qquad f(n+1)=1+f\bigl(n+1-f(f(n))\bigr)\,,\quad\hbox{for $n\ge0$.}
\enddisplay

\bugonpage 492, line 12 from the bottom (25 Jul 89)

\noindent
\equ(3.7\rm(d)), and \equ(3.8);
and this is equivalent to $n\{x\}<1$, when $n$~is a positive\cutpar

\bugonpage 494, line 19 (10 Oct 89)

\noindent
Aha. This goes down further and further, implying that $K_0\le0$;
but $K_0=1$.

\bugonpage 494, lines 3 and 4 from the bottom (16 Nov 89)

\noindent
solution can be written in a nice form discovered
by Carl "Witty":
\begindisplay
a_{n-1}=2^l+\biggl\lfloor\left(n-l\over2\right)^{\!2}\biggr\rfloor\,,
\qquad\hbox{when $2^l+l\le n<2^{l+1}+l+1$.}
\enddisplay

\bugonpage 495, line 17 (6 Jun 89)

\noindent
that $x\ge0$. The terms are bounded by $2^k$ as $k\to-\infty$ and by
$x^2/2^k$ as\cutpar

\bugonpage 496, line 3 (25 Jul 89)

\noindent
board.)
(b)~$f(n,k)=4\lfloor\sqrt{r^{2\mathstrut}-k^2}\rfloor$.

\bugonpage 496, new paragraph before answer 3.35 (25 Jul 89)

A more direct solution can be based on the identities $\lceil\lg 2j\rceil=
\lceil \lg j\rceil+1$ and $\lceil\lg(2j-1)\rceil=\lceil\lg j\rceil+\[j>1]$,
for $j\ge1$.

\bugonpage 499, lines 15--17 (25 Jul 89)

\textindent{3.45}%
 Let $\alpha>1$ satisfy $\alpha+1/\alpha=2m$.
\g Too easy.\g
Then we find
$2Y_n=\alpha^{2^n}+\alpha^{-2^n}$, and it follows that
$Y_n=\bigl\lceil\alpha^{2^n}\!/2\bigr\rceil$.

\bugonpage 499, lines 3 and 4 from the bottom (25 Jul 89)

\textindent{3.48}%
 (Solution by Heinrich "Rolletschek".) We can replace $(\alpha,\beta)$
\g A more interesting (still unsolved) problem: Restrict both $\alpha$
and $\beta$ to be $<1$, and ask when the given multiset determines the
unordered pair~$\{\alpha,\beta\}$.\g
by $(\{\beta\},\allowbreak{\alpha+\lfloor\beta\rfloor})$
 without changing $\lfloor n\alpha
\rfloor+\lfloor n\beta\rfloor$. Hence the condition $\alpha=\{\beta\}$ is
necessary. It is also sufficient: Let $m=\lfloor\beta\rfloor$ be the least
element of the given multiset, and let $S$ be the multiset obtained from the
given one by subtracting $mn$ from the $n$th smallest element, for all~$n$.
If $\alpha=
\{\beta\}$, consecutive elements of~$S$ differ by either $0$ or~$2$, hence
the multiset $\half S=\spec(\alpha)$ determines $\alpha$.

\bugonpage 501, line 2 (6 Jun 89)

\noindent
$y\=0$ \tmod3. We must have $y=0$ or $3$, and $x=0$ or $1$.

\bugonpage 521, lines 7--12 from the bottom (22 Nov 89)

\textindent{5.79}%
 (a) The sum is $2^{2n-1}$, so the gcd must be a power of~$2$.
If $n=2^kq$ where $q$~is odd, $2n\choose1$ is divisible by $2^{k+1}$
and not by~$2^{k+2}$. Each $2n\choose 2j+1$ is divisible by $2^{k+1}$
(see exercise~36), so this must be the gcd.
(b)~If $p^r\le n+1<p^{r+1}$, we get the most radix~$p$ carries by adding
$k$ to $n-k$ when $k=p^r-1$. The number of carries in this case
is $r-\epsilon_p(n+1)$, and $r=\epsilon_p\bigl(L(n+1)\bigr)$.

\smallskip
\textindent{5.80}%
 First prove by induction that $k!\ge(k/e)^k$.

\bugonpage 530, line 5 (6 Jun 89)

\noindent
Similarly if $6n+1$ is prime, the numerator of $\sum_{k=1}^{4n}(-1)^{k-1}\!/k
=H_{4n}-H_{2n}$ is\cutpar

\bugonpage 551, lines 6 and 7 from the bottom (26 Jun 89)

\textindent{8.11}%
 For example, let $K=k$ with probability $4/(k+1)(k+2)(k+3)$,
for all integers $k\ge0$. Then $EK=1$, but $E(K^2)=\infty$.
(Similarly we can construct random variables with finite cumulants
through $\kappa_m$ but with $\kappa_{m+1}=\infty$.)

\bugonpage 551, bottom four lines (30 Nov 89)

\textindent{8.12}%
 (a) Let $p_k=\Pr(X=k)$. If $0<x\le1$, we have $\Pr(X\le r)=
\sum_{k\le r}p_k\le\sum_{k\le r}x^{k-r}p_k\le\sum_k x^{k-r}p_k=x^{-r}P(x)$.
The other inequality has a similar proof. (b)~Let $x=\alpha/(1-\alpha)$ to
minimize the right-hand side.
(A more precise estimate for the given sum
is obtained in exercise 9.42.)

\bugonpage 555, bottom four lines (30 Nov 89)

\noindent
$\Pr\pbigi((S-6)^2\ge94^2\bigr)\le 22/94^2\approx.0025$.
(c)~The second tail equality says that $\Pr(S\ge100)\le1/x^{98}(4-2x-x^2)$
for all $x\ge1$, and we get the upper bound $0.00000005$ when $x=(\sqrt{49001}
-99)/100$. (The actual probability is approximately
$0.0000000009$, according to exercise 37.)

\bugonpage 558, line 11 (6 Jun 89)

\noindent
$m^{-n}m!{n-1\brace l-1}
/(m-l)!$. (The problem discussed in this exercise is traditionally\cutpar

\bugonpage 575, line 1 (7 Sep 89)

\textindent{9.53}%
 By induction, the $O$ term is $(m-1)!^{-1}\int_0^x t^{m-1}
f^{(m)}(x-t)\,dt$. Since\cutpar

\bugonpage 577, lines 9 and 10 from the bottom (13 May 89)

\noindent
"Euler" knew ([85$'@$] and [88, Part~2, \S92]).
Integrating again yields the desired formula. (This solution
was suggested by E.\thinspace M.\thinspace E. "Wermuth";
Euler's original derivation did not meet modern standards of rigor.)

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

\bugonpage 584, marginal note for number 88 (13 May 89)

\noindent\g48, 253, 577.\g

\bugonpage 588, publication update (12 Jul 89)

\bib 130
R.\,L. "Graham" and D.\,E. "Knuth", ``Problem E\thinspace2982: A double
infinite sum for $\vert x\vert$,''
{\sl American Mathematical Monthly\/ \bf96} (1989), 525--526.

\bugonpage 588, publication update (6 Jul 89)

\bib 146
J.\,M. Hammersley, ``An undergraduate exercise in manipulation,''
{\sl The Mathematical Scientist\/ \bf14} (1989), 1--23.

\bugonpage 594, number 227 (4 Jun 89)

\bib 227
Blaise "Pascal", ``Trait\'e du triangle arithmetique,'' in his
{\sl Trait\'e du Triangle Arithmetique, avec quelques autres petits
% sic --- accents are missing in original, including on contents page
% where caps and lowercase are mixed; "trait\'e" has the only accent
traitez sur la mesme matiere},\cutpar

\bugonpage 595, number 237 (18 Nov 89)

\bib 237
G. "P\'olya", \kern-2.51pt``Kombinatorische Anzahlbestimmungen f\"ur Gruppen,
Graphen und chemische Verbindungen,'' {\sl Acta Mathematica\/ \bf68}
(1937), 145--254.

\bugonpage 595, number 240 (17 Nov 89)

\bib 240
G. "P\'olya" and G. "Szeg\"o", % [sic] from original title page
 {\sl Aufgaben und Lehrs\"atze
aus der Analy\-sis}, two volumes. \ Julius Springer, Berlin, 1925;
fourth edition, 1970 and 1971.
English translation, {\sl Problems and Theorems in Analysis}, 1972 and~1976.

\bugonpage 597, second line of number 271 (17 Nov 89)

zadache o pervom nastuplenii redkogo sobyti\t\i a,''
{\sl Teori\t\i a vero\t\i atnoste\u\i}\cutpar

\bugonpage 599, new entry (16 Nov 89)

\bib{296$\kern-1pt'$}
\g604.\g
William C. "Waterhouse", ``Problem E\thinspace3117: Even odder than we
thought,'' {\sl American Mathematical Monthly\/ \bf94} (1987), 691--692.

\parindent=30pt % for the Credits

\bugonpage 602, left column (25 Jul 89)

\item{1.11}Inspired by Wood [307].

\bugonpage 603, right column, lines 17--18 (22 Nov 89)

\item{5.79}Mendelsohn [215]; Montgomery [218].

\bugonpage 604, right column (16 Nov 89)

\item{7.49}Waterhouse [296$@'$].

\parindent=0pt % for the Index

\bugonpage 607, right column (30 Nov 89)

Binomial theorem, 162--163, 199, 206, 221.

\bugonpage 609, right column (16 Nov 89)

de Moivre, Abraham, 283, 467, 582.

\bugonpage 611, right column (16 Nov 89)

exp: Exponential function, 441.

\bugonpage 614, left column (30 Nov 89)

Hoare, Charles Antony Richard, 28, 73, 589.

\bugonpage 616, left column (16 Nov 89)

Mallows, Colin Lingwood, 492.

\bugonpage 618, left column (10 Nov 89)

Pentagon,  300 (exercise 46), 416, 420.

\bugonpage 618, under Prime numbers (18 Nov 89)

\quad largest known, 109--110.

\bugonpage 619, left column (17 Nov 89)

Raney, George Neal, 345, 348, 595, 604.

\bugonpage 619, right column (25 Jul 89)

Rolletschek, Heinrich, 499.

\bugonpage 620, right column (18 Nov 89)

Steinhaus, Hugo Dyonizy, 605.

\bugonpage 621, under Sums (30 Nov 89)

\quad formal, 307, 317--318.

\bugonpage 621, right column (16 May 89)

Sun Ts\u{u}, 126.

\bugonpage 622, left column (30 Nov 89)

Tail inequalities, 414, 416.

\bugonpage 623, several for the left column (16 Nov 89)

Waterhouse, William Charles, 599.\par
Wermuth, Edgar Martin Emil, 577.\par
Witty, Carl Roger, 494.

\bye
