Concrete Mathematics, Second Edition

Here is a list of all significant changes that were made between January 1998 and May 2013. An asterisk (*) marks technical errors that are not merely typographical:

*page vi, line 9 from the bottom

change "finite" to "definite"

page ix, line 5 from the bottom

change "paid to the first finder of any" to "conveyed to anyone who is the first to report any"

page 8, line 2 from the bottom

change "1" to "$1$"

page 14, line 10 from the bottom

change "$\gamma$;" to "$\gamma$."

page 20, in 21

change m to q (four times)

page 22, line 4

change "Greek letter $\sum$" to "Greek letter $\Sigma$"

page 22, line 7

change "1" to "$1$"

pages 28 and 29

(beginning with the 21st printing, recurrence (2.12) is changed to more realistic equations in which $C_1=0$ and the summation rule is used only for $n>1$; this implies several dozen changes to the exposition; the previous form with $C_1=2$ was inconsistent with real quicksort implementations)

page 30

a new graffito near (2.16): "My other math books have different definitions for these laws."

*page 36, line 13

change "$K(j)=J'(k)$ be the basic" to "$K(j)$, $J'(k)$ be sets that correspond to the basic"

page 41, line 2 from the bottom

change "at least seven" to "at least eight"

page 43, line 16

change "the induction" to "the inductive step"

page 44, line 10

change "first n integers" to "first few nonnegative integers"

page 45, line 5

change "(2.41)" to "(2.40) and (2.41)"

page 45, line 3 from the bottom

change "between 0" to "between $0$"

page 55, last three lines of Table 55

change $f$ to $u$ and $g$ to $v$ (12 changes)

*page 58, line 20

change $\sum_{k=0}^{n}$ to $\sum_{k=0}^{n-1}$

page 60, line 7

change "or $x^-=0$" to "or $x^-=0$, or both"

page 64, in exercise 26

change "double product" to "double product P="

page 65, exercise 31

change " Riemann's" to "Riemann's"

page 71, line 13 from the bottom

change "function with" to "function on an interval of the real numbers, with"

page 71, bottom line

change "$x$ and $\lceil x\rceil$" to "$\lfloor x\rfloor$ and $\lceil x\rceil$"

page 75, line 6

white out the little dot to the left of the \sum sign

page 83, new graffito for the margin (just below (3.23))

"Notice that $x\mathbin{\rm mumble}y=(-x)\mathbin{\rm mod}y$."

*page 88, new sentence to follow line 5

We can assume without loss of generality that $0<\alpha<1$.

*page 88, lines 12 and 13

change "Without ... let us" to "Let us"

page 105, line 4 from the bottom

change "others that have ... more divisors" to "others that have nontrivial divisors"

page 106, line 4 from the bottom

change "This contradiction" to "Hence $p_1$ must be either $q_2$ or $\cdots$ or $q_n$; yet $p_1$ is strictly smaller! This contradiction"

page 108, lines 5--7

change "This contradicts ... infinitely many." to "Every finite set of prime numbers must therefore be incomplete."

page 108, line 6 from the bottom

change "smallest factor" to "smallest prime factor"

page 112, line 12

change "and its" to "and $k=n$, while it has its"

page 112, bottom line

change "powers-of-2" to "powers-of-$2$"

page 119, line 20

change "$0\le b<a<n$" to "$0\le b<a\le n$"

*page 120, line 8

change "following S" to "following f(S)"

page 130, line 5 from the bottom

change "with the possible exception of" to "including"

page 136, lines 4, 5, 6, 11 from the bottom

use larger parentheses around the displayed fractions

page 144, line 4 from the bottom

change "all solutions" to "all relevant solutions"

page 147, line 2 of exercise 37

change "log" to "ln"

page 147, line 1 of exercise 38

change $a>b$ to $a>b>0$

page 162, bottom line

change "and we" to "unless $r$ is a nonnegative integer, and we"

page 169, generalization of identity (5.26)

change "$\sum_{0\le k\le l}$" to "$\sum_{-q\le k\le l}$"; the conditions are now "integers $m,n\ge0$, integer $l+q\ge0$."

page 171, line 7

change "integers m,n\ge0" to "integers m,n"

page 180, line 20

change "using (5.7)" to "using (5.6) and (5.7)"

page 182, line 7

change (5.6) to (5.5)

page 184, line 5

change "between 0" to "between $0$"

page 206, line 6

change "using (5.56)" to "using (5.13) and (5.14)"

page 206, line 8 from the bottom

change "form a field" to "with $-\infty<n<\infty$ form a field"

page 221, line 17

change "$D^k F(k)$" to "$D^k F(z)$"

page 229, line 2 from the bottom

change "383" to "384"

*page 230, line 10

change "summable." to "summable, using ideas pioneered by Sister Celine Fasenmyer in the 1940s [382]."

page 231, line 8

change "$q$ and" to "$q$, and" (twice)

page 233, line 12 from the bottom

change "$\beta_0$, \dots\ $\beta_l$" to "$\beta_0$, \dots, $\beta_l$"

*page 239, line 7 from the bottom

change "$k$; see exercise 107." to "$k$."

page 243, line 1

change " Which" to "Which"

page 245, bottom line

change "binomial number system" to "combinatorial number system"

page 246, replacement for the second line of exercise 42

$\sum_{k=0}^m (-1)^k/{n\choose k}$ in closed form when $0\le m\le n$.

*page 247, top line

change "$\sum_{k\le n}$" to "$\sum_{k=0}^n$"

page 248, top line

change "Use" to "Given $n$ and $z$, use"

*page 253, line 4 from the bottom

change "constant $\alpha$" to "constant $\alpha\ne0$"

page 254, line 8

change " What" to "What"

page 268, displayed equation (6.34)

change "0;" to "0."

page 273, just below the illustration

change "we require the edges of the cards" to "we assume that card $k$ rests on card $k+1$, for $1≤k<n$. We also require the right edge of each card"

page 276, line 16

change "if n is in" to "if 1/n is in"

page 288, graffito

change "Johann" to "(Johann"; also change "1635" to "1631"

page 292, line 19 from the bottom

change "Édouard" to "Edouard"

page 295, new graffito to be placed near (6.113)

[The anonymous author of a classic Sanskrit work, Prākṛta Paiṅgala (c. 1320), actually knew this representation many centuries ago.]

*page 299, line 2 from the bottom

change "Leonhard Euler [113] in 1765" to "Daniel Bernoulli in 1728"

page 302, line 17

change "Euler observed" to "Euler [112] observed"

page 312, last line of exercise 31

change ".)." to ".)"

page 332, equation (7.15)

squeeze things together so that the period doesn't overlap the equation number

page 338, line 2 from the bottom

change "for $z$" to "for $z$ and multiplying by $a$"

page 358, line 6 from the bottom

change "$a_2\ldots$" to "$a_2,\ldots$"

page 360, line 4

change "$k\ge0$" to "k>0"

page 361, lines 8 and 9

change "call this a Fuss-Catalan number" to "call it the Fuss--Catalan number"

page 373, line 8

change "$\cdots n$" to "$\cdots+n$" below the summation sign

page 385, line 12

change "that X can assume" to "for which Pr(X<x) is nonzero"

page 385, lines 12 and 15

chance "all $x$" to "all $x\in X(\Omega)$"

page 386, line 6 from the bottom

change "random dice" to "fair dice"

*page 417, lines 7 and 8 from the bottom

insert a plus sign at the beginning of each line

page 437, line 10

change "$(X,Z)$ and" to "$(X,Z)$, and"

page 440, line 12 from the bottom

change "growth ratios" to "rates of growth"

page 442, line 12

change "is constant" to "is a nonzero constant"

page 442, line 2 from the bottom

change "is in" to "are in"

page 443, graffito

change "... wir" to "..., wenn wir"; also replace the uses of German sharp-s by "ss" (twice)

page 444, line 20

change "de Bruijn's `L(n)'" to "the quantity L(n) above"

page 445, addition to the graffito

"-- Michael Stueben"

page 449, line 12 from the bottom

change "base-10" to "base-$10$"

page 457, line 12

change $\pi(n)$ to $\pi(p)$

page 457, bottom line

change $\pi(n)$ to $\pi(p)$

*page 463, line 3 from the bottom

change $O(n)$ to $n\ln\ln n + O(n)$

page 500, in answer 1.21

change m to q (twice), and "an m" to "a q"

page 501, line 2 of answer 1.26

change m to q

page 502, line 7

change "doesn't hold" to "doesn't apply"

page 503, line 11

change "$...n!$= $S_{n-1}...$" to "$...n! = S_{n-1}...$"

page 508, line 7 from the bottom

change $n>0$ to $n\ge0$

*page 512, lines 11 and 12 from the bottom

change "a segment of length $2k$" to "a segment of length $2k-1$"; also change "a segment of length $2k-2$" to "the interior of a segment of length $2k$"

page 516, line 2 from the bottom

change "20000" to "49081"

page 518, line 2 from the bottom

change "$S(3),\ldots,\rangle$" to "$S(3)\ldots\,\rangle$"

*page 519, lines 4 and 5 from the bottom

change $m_2<n_2$ to $m_2\le n_2$ (twice)

*page 520, line 10

change "90%" to "80%"

*page 522, line 4

change "1300" to "13000"

*page 522, line 11

add the qualification "integer $m\ge2$,"

*page 522, line 13

change "\lfloor n/m\rfloor" to "4\lfloor n/m\rfloor + [n mod m=m-1] - [n mod m=0]"

page 522, in exercise 56

change "stated product" to "stated fraction" (twice)

*page 523, line 11 from the bottom

change "cp^\theta" to "p^\theta" (twice)

*page 524, line 9

change "divisor d" to "divisor d>2"

page 530, replacement for the 4th line of answer 42

$$\sum_{k=0}^m(-1)^k/{n\choose k}=(-1)^{x-1}{n+1\over n+2}\Big/{n+1\choose x}\Bigr\vert_0^{m+1}={n+1\over n+2}+\Bigl({m+1\over n+2}\Bigr){(-1)^m/{n\choose m}}.$$

*page 535, lines 4 and 5 of answer 5.69

change "n" to "m" in two places where n occurs by itself

*page 536, replacement for lines 5--7

$m(m-n)\ldots(m-(k-1)n)$ at least $r$ times if $p^r$ divides $k!$, because we have $m(m-n)\ldots(m-(k-1)n)\equiv n^k(mn')^{\underline k}= k!\,n^k{mn'\choose k}\equiv0$ (mod $p^r$) when $nn'\equiv1$.

*page 537, lines 2 and 3 from the bottom

the left-hand side of the first equation should be simply $zt{\cal B}_t(z)^{-1}{\cal B}'_t+1$, and the second equation should be corrected in the analogous way

*page 537, line 2 from the bottom

replace $\cal E$ by ${\cal E}_t$ in right-hand side of this equation

*page 540, answer 5.94

change $k$ to $k-1$

page 550, line 6

change "104.607361" to "104.60736"

*page 550, line 2 from the bottom

change "a and b odd" to "b odd"

page 551, new graffito near answer 6.24

(Of course Euler knew the Genocchi numbers long before Genocchi was born; see [110], Volume 2, Chapter 7, §181.)

*page 554, line 16 from the bottom

change $H_r+\sum$ to $H_r-\sum$

*page 555, new display replacing line 7

S_m(p)=\sum_{k=0}^{p-1}\sum_{j=0}^m{m\brace j}k^{\underline j} = \sum_{j=0}^m{m\brace j}{p^{\underline{j+1}}\over j+1} \equiv 0.

page 559, answers 74 and 75

[I'm changing the notation for Euler numbers to agree with papers in combinatorics instead of papers in numerical analysis: Now $T_n(1)=2^nE_n$ for all $n\ge0$.]

*page 564, comment regarding answer 6.91

An elegant solution to this research problem has been found by Philippe Flajolet and Helmut Prodinger, SIAM Journal on Discrete Mathematics 12 (1999), 155--159.

page 564, improvement to answer 6.94

change "has the form ... where" to "equals $\sum_k(wF(\alpha'+\beta'+ \gamma',\alpha'+\beta',\alpha')+zF(\alpha+\gamma,\alpha+\beta,\alpha))^k(1)$, where"

page 564, line 6 from the bottom

change "382" to "383"

page 564, new answer for exercise 6.95

An elegant solution to this research problem was found by Manuel Kauers, Journal of Symbolic Computation 42 (2007), 948--970.

page 568, line 11 from the bottom

make the third ")" larger

page 569, line 8

delete the first "(" on this line

page 570, line 2 from the bottom

change "$A_n=\vert E_n\vert+T_n$ is a" to "$A_n$ is the Euler number $E_n$ of exercise 6.74, namely a"

page 571, line 2 from the bottom

insert a plus sign after $2/p^4$

page 575, answer to research problem 7.57

change "currently offers $500 for a solution" to "repeatedly offered $500 for a solution to this problem"

page 576, line 15 from the bottom

change "G(y)" to "G(Y)"

*page 580, line 9

change "$S_A(A:B)+S_B(B:C)$" to "$S_A(A:C)+S_B(B:C)$"

page 585, line 10 from the bottom

change "p_{mn}" to "p_{m,n}"

*page 590, line 12 from the bottom

change "p\perp q. And (p+1)\divides" to "pq>0 and p+q="

*page 599, line 8

change "$O(k^3m^{-2}\log n)$" to "$O(k^3m^{-2}\log n)+O(m^{-1})$"

page 600, line 14 from the bottom

change "($a$)" to "(a)"

page 604, reference 3

add new sentence: "[See also P. E. Böhmer, ``Über die Transzendenz gewisser dyadischer Brüche,'' Mathematische Annalen 96 (1927), 367--377, 735.]"

page 605, in reference 16

change "[See also ... 246.]" to "[This triangle was first found by L. Seidel, ``Ueber eine einfache Entstehungsweise der Bernoulli'schen Zahlen und einiger verwandten Reihen,'' Sitzungsberichte der mathematisch-physikalischen Classe der königlich bayerischen Akademie der Wissenschaften zu München 7 (1877), 157--187.]"

page 605, marginal notes for references 15 and 16

interchange these; [15] is cited on page 633 and [16] on page 635.

page 607, reference 40

change "6 (1860)" to "3 (1861)"

page 607, reference 49

insert closing quotes before Portugaliae

page 608, references 57 and 58

(I should have transcribed the titles using the 19th-century Russian orthography of the original publications)

page 609, lines 3 and 4 of reference 77

change "math- ematische" to "ma- thematische"

page 610, reference 87

change "25 May 1902" to "15 November 1896, 25 May 1902,"

page 611, marginal note for reference 103

change "278." to "277, 278."

page 613, reference 119

change "Faulhabern" to "Faulhaber"

page 613, reference 122

change "Leonardo Fibonacci [Pisano]" to "Leonardo filio Bonacci Pisano [Fibonacci]"

page 615, reference 149

add closing double-quotes after the comma before Messenger

page 617, reference 176

change "its Applications" to "Its Applications"

page 617, reference 180

change "(1944)" to "(1945)"

page 618, reference 193

change "Structures and" to "Structures &"

page 620, marginal note for reference 220

change "267." to "267, 598."

page 621, reference 235, add a new sentence

[More general formulas had been published by L. Toscano, Commentationes 3 (Vatican City: Accademia della Scienze, 1939), 721--757, Equations 17 and 117.]

page 622, reference 249

change "Zhaī" to "Zhāi"

page 623, reference 263

change "Maclaurin" to "MacLaurin"

page 628, reference 331

change "eë" to "ee"; also change "its Applications" to "Its Applications"

page 628, a new reference

336' Tor B. Staver, ``Om summasjon av potenser av binomiaalkoeffisientene,'' Norst Matematisk Tidsskrift 29 (1947), 97--103. [Cited on page 634.]

page 630, last line of Venn's citation (reference 359)

change "9" to "10"

page 630, a new reference

361' J. Wasteels, ``Quelques propriétés des nombres de Fibonacci,'' Mathesis, series 3, 11 (1902), 60--62. [Cited on page 635.]

*page 631, new entry for bibliography (cited on page 230)

382 Doron Zeilberger, ``Sister Celine's technique and its generalizations,'' Journal of Mathematical Analysis and Applications 85 (1982), 114--145. See also Sister Mary Celine Fasenmyer, ``A note on pure recurrence relations,'' American Mathematical Monthly 56 (1949), 14--17. [Also renumber the former entries 382 and 383, which now become 383 and 384.]

page 633, right column entry for 3.53

change ".*." to ".*"

page 634, left column, entry for 5.38

change "1.2.6--16" to "1.2.6--56"

page 634, right column, new entry

5.100 Staver [336'].

page 635, left column, replacement entry

6.44 Wasteels [361'].

page 637, upper right corner

in some printings the spurious word "INDEX" appeared here

page 637, left column, entry for $\Phi$

change "137--139" to "138--139"

page 637, right column, entry for $\sim$

change "428--429" to "110, 439--443, 448--449"

page 638, left column, under algorithms, Euclid's

change "103" to "103--104"

page 638, left column, under algorithms, Gosper-Zeilberger

change "255" to "255, 319, 547"

page 638, left column, entry for Alice

change "430" to "427, 430"

page 638, right column, entry for baseball

change "648" to "622, 638"

page 638, right column

change "Bernoulli, Daniel Julius" to "Bernoulli, Daniel"

page 639, left column, entry for Bernoulli numbers

denominators of, 315, 551, 574; numerators of, 555

page 639, left column, entry for Bill

change "430" to "427, 430"

page 639, left column, entry for binary logarithm

change "70" to "70, 449"

page 639, right column

delete "binomial number system, 245"

page 639, right column, new entry

"Böhmer, Paul Eugen, 604"

page 640, left column, under cards, stacking

change "280" to "278"

page 640, right column, entry for closed form

change "321" to "321, 331"

page 640, right column, new entry

"combinatorial number system, 245"

page 641, left column, entry for computer algebra

change "268" to "254"

page 641, left column, entry for convergence

of power series, 206, 331--332, 348, 451, 532

page 641, right column, entry for Coxeter

change "Macdonald" to "MacDonald"

page 641, right column, entry for cyclic shift

change "362" to "359, 362"

page 641, right column, entry for deg

change "226" to "227"

page 641, right column, entry for derangements

derangements, 194--196, 250

page 642, right column, entry for Doyle

change "Arthur Conan" to "Arthur Ignatius Conan"

page 643, left column

add page 551 under Euler, Leonhard

page 643, left column, entry for Euler's constant

change "319" to "316, 319"

page 643, right column, entry for F

change "hypergeometric functions" to "hypergeometric series"

page 643, right column, entry for fair dice

change "417" to "392, 417, 429"

page 644, left column, new entry

"Fasenmyer, Mary Celine, 230, 631"

page 644, left column, under Fibonacci, addition

change "317" to "318"

page 644, right column, entry for fractions, unit

change "95" to "95, 101"

page 645, left column, entry for games

change "Penny" to "Penney"

page 645, left column, Gauss entry

change "Johann Friedrich" to "Johann Friderich"

page 645, right column, under Gosper algorithm, examples

change "534" to "530, 534"

page 645, right column, under graphs of functions, 1/x

change "262--263" to "276--277"

page 645, right column, under graphs of functions, partial sums of a sequence

change "345--346" to "359--360"

page 646, left column

change "Håland" to "Håland Knutson"

page 646, right column, under hypergeometric series, partial sums of

change "230, 224" to "230"

page 647, right column, new entry

"Kauers, Manuel, 564"

page 648, left column, Lekkerkerker entry

change "Cornelius" to "Cornelis"

page 648, left column, entry for lg

change "70" to "70, 449"

page 648, left column, Li Shan-Lan entry

change "Rénshū (=" to "(= Rénshū ="

page 648, left column, entry for ln

change "276" to "276, 449"

page 648, left column

change "Loú Shìtūo" to "Lóu, Shìtuó"

page 648, right column

change "Maclaurin" to "Maclaurin (= Mac Laurin)"

page 649, left column, entry for natural logarithm

change "276" to "276, 449"

page 649, under number system

change "binomial" to "combinatorial"

page 650, right column, under permutations, excedances in

change "314" to "316"

page 650, right column, under permutations, fixed points in

change "418" to "428"

page 650, right column, under permutations, left-to-right maxima in

change "314" to "316"

page 650, right column, under Pfaff, reflection law

change "247" to "244, 247"

page 650, right column, under phi, in solutions to recurrences

change "285--286" to "299--301"

page 650, right column, entry for pi

change "3.14159" to "3.14159)"

page 650, right column, entry for Phi function

change "137--139" to "138--139"

page 650, right column, entry for Pisano

Pisano, Leonardo filio Bonacii, 613, see Fibonacci

page 651, left column, under prime numbers, Mersenne

change "522" to "522--523"

page 651, right column, entry for probability distributions

change "367" to "381"

page 651, right column, entry for probability distributions, uniform

change "420--421" to "418--421"

page 651, right column, entry for Rahman

change "Mizanur" to "Mizan"

page 652, left column, entry for recurrences, implicit

change "136--138, 193--194" to "136--139, 193--195"

page 652, left column, new entry

regular expressions, 278

page 652, right column, entry for Saalschütz

change "627, 634" to "627"

page 653, left column

Seidel, Philipp Ludwig von, 605

page 653, left column, entry for Sierpiński

change "Wacław" to "Wacław Franciszek"

page 653, right column, new entry

Staver, Tor Bøhm, 628, 634

page 654, left column, new entry

Stueben, Michael, 445

page 655, left column, entry for tail of a sum

change "452--455" to "466--469, 488--489, 492"

page 655, left column, entry for tangent numbers

change "620" to "570, 620"

page 655, right column, entry for trivial

change "129" to "105, 129"

page 655, left column, new entry

Toscano, Letterio, 621

page 655, right column, entry for uniform distribution

change "418--419" to "418--421"

page 656, left column, new entry

Wasteels, Joseph, 630, 635

page 656, right column, second entry for Yao

change "Foong Frances" to "Frances Foong Chu"

page 656, right column, third entry for Yao

change "Yaó" to "Yáo"

back cover, line 1 at the top right

change "Graham ," to "Graham,"

A dozen or so entries in the bibliography have been updated to refer to items that have been reprinted in the author's Selected Papers. As a result, several bibliographic entries now appear on different pages than they used to.

One reader has also pointed out that the formulas in this book mix two slightly different styles of commas. All commas should actually have the same style as the "concrete roman" commas in the text.

Concrete Mathematics home page

Don Knuth's home page

Don Knuth's other books