index.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Index for Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac

\pageno=637

\beginchapter {} Index

WHEN AN INDEX ENTRY refers to a page containing a relevant exercise,
the answer to that exercise (in Appendix~A) might divulge further
\g (Graffiti have been indexed too.)\g
information; an answer page is not indexed here unless it refers to a topic
that isn't included in the statement of the relevant exercise.
Some notations not indexed here (like $x\_n$, $\lfloor x\rfloor$,
and $n\euler m$) are listed on pages x and~xi, just before
the table of contents.\looseness=-1

\newbox\partialpage
\output={\global\setbox\partialpage=\vbox{\unvbox255\bigskip}}\eject
\advance\vsize-\ht\partialpage

 \textfont0=\gmathtext
  \scriptfont0=\gmathsubtext
  \scriptscriptfont0=\gmathsubsubtext
 \textfont1=\gmathlet \let\tfont=\gtfont
  \scriptfont1=\gmathsublet
  \scriptscriptfont1=\gmathsubsublet
 \textfont2=\gmathsym
  \scriptfont2=\gmathsubsym
  \scriptscriptfont2=\gmathsubsubsym
 \textfont3=\gmathext
  \scriptfont3=\gmathsubext
  \scriptscriptfont3=\gmathsubsubext
\textfont\scrfam=\gmathscr
 \scriptfont\scrfam=\gmathsubscr
 \scriptscriptfont\scrfam=\gmathsubsubscr
\textfont\frfam=\gmathfr
 \scriptfont\frfam=\gmathsubfr
 \scriptscriptfont\frfam=\gmathsubsubfr
\textfont\euexfam=\gmatheuex
\scriptfont\euexfam=\gmathsubsym % OK since I don't use all chars in this size
\textfont\eqfam=\nineeq
 \def\rm{\fam0 \gmathtext}%
 \let\oldsty=\goldstyle
 \let\big=\ninebig
 \setbox\strutbox=\hbox{\vrule height7.25pt depth2.75pt width0pt}%
 \gmathtext % that's 9pt roman
\rightskip0pt plus4em \spaceskip.3333em \xspaceskip.5em
\baselineskip 12pt plus.2pt minus.2pt
\parindent=0pt
\everypar{\hangindent=20pt}
\def\sub{{\penalty50\parskip=0pt\leavevmode}\kern10pt\hangindent=30pt}
\hsize=2.75in
\newif\ifright \newbox\leftcol
\output{\ifright\twocolumnout\global\rightfalse
  \else\leftcolumnsave\global\righttrue\fi}
\def\leftcolumnsave{\global\setbox\leftcol=\box255}
\def\twocolumnout{\shipout\vbox to\totheight{ % here we define 1 page of output
    \offinterlineskip % butt the boxes together
    \vbox to 2pc{ % this part goes on top of the regular pages
      \ifodd\pageno \rightheadline\else\leftheadline\fi
      \vfill} % this completes the \vbox to 2pc
    \ifvoid\partialpage\else\global\advance\vsize\ht\partialpage
      \ifodd\pageno\moveright7pc\fi \box\partialpage\fi
    \hbox to35pc{\box\leftcol\hss\box255}
    \vfill
    \iftitle \global\titlefalse % reset the titlepage switch
	\ifodd\pageno \hbox to35pc{\hfil\foliofont\folio}
	\else\hbox{\foliofont\folio}\fi\fi
    \ifpreprint\ifinxmode\makeinxfooter\fi\fi
    }
  \advancepageno}
\exhyphenpenalty=10000
\def\=#1{{\accent22 #1}}
\def\see{{\ninesl\kern1pt see\/} }
\def\also{{\ninesl\kern1pt see also\/} }
\def\cpage{657} % colophon page
\obeylines
$0^0$, 162
$\sqrt2$ ($\approx1.41421$), 100
$\sqrt3$ ($\approx1.73205$), 378
$\Im$: imaginary part, 64
$\frak L$: logarithmico-exponential functions, 442--443
$\Re$: real part, 64, 212, 451
$\gamma$ ($\approx0.57722$), \see Euler's constant
$\Gamma$, \see Gamma function
$\delta$, 47--56
$\Delta$: difference operator, 47--55, 241, 470--471
$\epsilon_p(n)$: largest power of $p$ dividing~$n$, 112--114, 146
$\zeta$, \see zeta function
$\vartheta$, 219--221, 310, 347
$\Theta$: Big Theta notation, 448
$\kappa_m$, \see cumulants
$\mu$, \see M\"obius function
$\nu$, \see nu function
$\pi$ ($\approx3.14159$), 26, 70, 146, 244, 485, 564, 596
$\pi(x)$, \see pi function
$\sigma$: standard deviation, 388; \also Stirling's constant
$\sigma_n(x)$, \see Stirling polynomials
$\phi$ ($\approx1.61803$): golden ratio, 70, 97, 299--301, 310, 553
$\varphi$, \see phi function
$\Phi$: sum of $\varphi$, 137--139, 462--463
$\Omega$: Big Omega notation, 448
$\sum$-notation, 22--25, 245
$\prod$-notation, 64, 106
$\bigwedge$-notation, 65
$\Longleftrightarrow$: if and only if, 68
$\Longrightarrow$: implies, 71
$\divides$: divides, 102
$\edivides$: exactly divides, 146
$\rp$: is relatively prime to, 115
$\prec$: grows slower than, 440--443
$\succ$: grows faster than, 440--443
$\asymp$: grows as fast as, 442--443
$\sim$: is asymptotic to, 8, 428--429
$\approx$: approximates, 23
$\equiv$: is congruent to, 123--126
$\#$: cardinality, 39
$!$: factorial, 111--115
$\?$: subfactorial, 194--200
$\dts\,$: interval notation, 73--74
$\ldots\,$: ellipsis, 21, 50, 108, \dots
\medskip \advance\baselineskip-1pt
Aaronson, Bette Jane, ix
Abel, Niels Henrik, 604, 634
Abramowitz, Milton, 42, 604
absolute convergence, 60--62, 64
absolute error, 452, 455
absolute value of complex number, 64
absorption identities, 157--158, 261
Acton, John Emerich Edward Dalberg, Baron, 66
Adams, William Wells, 604, 635
Addison-Wesley, ix
addition formula for ${n\choose k}_{\mathstrut}$, 158--159
\sub analog for ${n\euler k}_{\mathstrut}$, 268
\sub analogs for $n\brace k$ and $\,n\,\brack k$, 259, 261
\sub dual, 530
Aho, Alfred Vaino, 604, 633
Ahrens, Wilhelm Ernst Martin Georg, 8, 604
Akhiezer, Naum Il'ich, 604
Alfred [Brousseau], Brother Ulbertus, 607, 633
algebraic integers, 106, 147
algorithms, analysis of, 138, 413--426
\sub divide and conquer, 79
\sub Euclid's, 103, 123, 303--304
\sub Fibonacci's, 95, 101
\sub Gosper's, 224--227
\sub Gosper-Zeilberger, 229--241, 254--255
\sub greedy, 101, 295
\sub self-certifying, 104
Alice, 31, 408--410, 430
Allardice, Robert Edgar, 2, 604
ambiguous notation, 245
American Mathematical Society, viii
AMS Euler, ix, \cpage
analysis of algorithms, 138, 413--426
analytic functions, 196
ancestor, 117, 291
Andr\'e, Antoine D\'esir\'e, 604, 635
Andrews, George W. Eyre, 215, 330, 530, 575, 605, 634, 635
answers, notes on, 497, 637, viii
anti-derivative operator, 48, 470--471
anti-difference operator, 48, 54, 470--471
Ap\'ery, Roger, 238, 605, 629, 634
\sub numbers, 238--239, 255
approximation, \see asymptotics
\sub of sums by integrals, 45, 276--277, 469--475
Archibald, Raymond Clare, 608
argument of hypergeometric, 205
arithmetic progression, 30, 376
\sub floored, 89--94
\sub sum of, 6, 26, 30--31
Armageddon, 85
Armstrong, Daniel Louis (= Satchmo), 80
Arnol'd, Vladimir Igorevich, 605, 635
art and science, 234
ascents, 267--268, 270
Askey, Richard Allen, 634
associative law, 30, 61, 64
asymptotics, 439--496
\sub from convergent series, 451
\sub of Bernoulli numbers, 286, 452
\sub of binomial coefficients, 248, 251, 495, 598
\sub of discrepancies, 492, 495
\sub of factorials, 112, 452, 481--482, 491
\sub of harmonic numbers, 276--278, 452, 480--481, 491
\sub of hashing, 426
\sub of $n$th prime, 110--111, 456--457, 490
\sub of Stirling numbers, 495, 602
\sub of sums, using Euler's summation formula, 469--489
\sub of sums, using tail-exchange, 466--469, 486--489
\sub of sums of powers, 491
\sub of wheel winners, 76, 453--454
\sub table of expansions, 452
\sub usefulness of, 76, 439
Atkinson, Michael David, 605, 633
Austin, Alan Keith, 607
automaton, 405
automorphic numbers, 520
average, 384
\sub of a reciprocal, 432
\sub variance, 423--425
\medskip
$B_n$, \see Bernoulli numbers
Bachmann, Paul Gustav Heinrich, 443, 462, 605
Bailey, Wilfrid Norman, 223, 548, 605, 634
Ball, Walter William Rouse, 605, 633
Banach, Stefan, 433
Barlow, Peter, 605, 634
Barton, David Elliott, 602, 609
base term, 240
baseball, 73, 148, 195, 519, 648, 653
BASIC, 173, 446
basic fractions, 134, 138
basis of induction, 3, 10--11, 320--321
Bateman, Harry, 626
Baum, Lyman Frank, 581
Beatty, Samuel, 605, 633
bee trees, 291
Beeton, Barbara Ann Neuhaus Friend Smith, viii
Bell, Eric Temple, 332, 605, 635
\sub numbers, 373, 493, 603
Bender, Edward Anton, 606, 636
Bernoulli, Jakob (= Jacobi = Jacques = James), 283, 470, 606
\sub numbers, \see Bernoulli numbers
\sub polynomials, 367--368, 470--475
\sub polynomials, graphs of, 473
\sub trials, 402; \also coins, flipping
Bernoulli, Johann (= Jean), 622
Bernoulli numbers, 283--290
\sub asymptotics of, 286, 452
\sub calculation of, 288, 620
\sub denominators of, 315
\sub generalized, \see Stirling polynomials
\sub generating function for, 285, 351, 365
\sub relation to tangent numbers, 287
\sub table of, 284, 620
Bernshte{\u\i}n (= Bernstein), Serge{\u\i} Natanovich, 636
Bertrand, Joseph Louis Fran\c{c}ois, 145, 606, 633
\sub postulate, 145, 500, 550
Bessel, Friedrich Wilhelm, functions, 206, 527
Beyer, William Hyman, 606
biased coin, 401
bicycles, 260, 500
Bieberbach, Ludwig, 617
Bienaym\'e, Ir\'en\'ee Jules, 606
Big Ell notation, 444
Big Oh notation, 76, 443--449
Big Omega notation, 448
Big Theta notation, 448
bijection, 39
Bill, 408--410, 430
binary logarithm, 70
binary notation (radix~$2$), 11--13, 15--16, 70, 113--114
binary partitions, 377
binary search, 121, 183
binary trees, 117
Binet, Jacques Philippe Marie, 299, 303, 606,~633
binomial coefficients, 153--242
\sub addition formula, 158--159
\sub asymptotics of, 248, 251, 495, 598
\sub combinatorial interpretation, 153, 158, 160, 169--170
\sub definition, 154, 211
\sub dual, 530
\sub generalized, 211, 318, 530
\sub indices of, 154
\sub middle, 187, 255--256, 495
\sub reciprocal of, 188--189, 246, 254
\sub top ten identities of, 174
\sub wraparound, 250~(exercise~75), 315
binomial convolution, 365, 367
binomial distribution, 401--402, 415, 428, 432
\sub negative, 402--403, 428
binomial number system, 245
binomial series, generalized, 200--204, 243, 252,~363
binomial theorem, 162--163
\sub as hypergeometric series, 206, 221
\sub discovered mechanically, 230--233
\sub for factorial powers, 245
\sub special cases, 163, 199
Blom, Gunnar, 606, 636
bloopergeometric series, 243
Boas, Ralph Philip, Jr., 600, 606, 636, viii
Boggs, Wade Anthony, 195
Bohl, Piers Paul Felix [= Bol', Pirs Georgievich], 87, 606
Bois-Reymond, Paul David Gustav du, 440, 610, 617
Boncompagni, Prince Baldassarre, 613
bootstrapping, 463--466
\sub to estimate $n$th prime, 456--457
Borchardt, Carl Wilhelm, 617
Borel, \'Emile F\'elix \'Edouard Justin, 606, 636
Borwein, Jonathan Michael, 606, 635
Borwein, Peter Benjamin, 606, 635
bound variables, 22
boundary conditions on sums,
\sub can be difficult, 75, 86
\sub made easier, 24--25, 159
bowling, 6
box principle, 95, 130, 512
bracket notation,
\sub for coefficients, 197, 331
\sub for true/false values, 24--25
Brahma, Tower of, 1, 4, 278
Branges, Louis de, 617
Brent, Richard Peirce, 306, 525, 564, 606
bricks, 313, 374
Brillhart, John David, 606, 633
Brocot, Achille, 116, 607
Broder, Andrei Zary, 632, ix
Brooke, Maxey, 607, 635
Brousseau, Brother Alfred, 607, 633
Brown, Mark Robbin, 632
Brown, Morton, 501, 607
Brown, Roy Howard, ix
Brown, Thomas Craig, 607, 633
Brown, Trivial, 607
Brown, William Gordon, 607
Brown University, ix
Browning, Elizabeth Barrett, 320
Bruijn, Nicolaas Govert de, 444, 447, 500, 609, 635, 636
\sub cycle, 500
bubblesort, 448
Buckholtz, Thomas Joel, 620
Bulwer-Lytton, Edward George Earle Lytton, Baron, v
Burma-Shave, 541
Burr, Stefan Andrus, 607, 635
\medskip
calculators, 67, 77, 459
\sub failure of, 344
calculus, vi, 33
\sub finite and infinite, 47--56
candy, 36
Canfield, Earl Rodney, 602, 607, 636
cards,
\sub shuffling, 437
\sub stacking, 273--274, 280, 309
Carlitz, Leonard, 607, 635
Carroll, Lewis (= Dodgson, Rev.~Charles Lutwidge), 31, 293, 607, 608, 630
carries,
\sub across the decimal point, 70
\sub in divisibility of $m+n\choose m$, 245, 536
\sub in Fibonacci number system, 297, 561
Cassini, Jean Dominique, 292, 607
\sub identity, 292--293, 300
\sub identity, converse, 314
\sub identity, generalized, 303, 310
Catalan, Eug\`ene Charles, 203, 361, 607
Catalan numbers, 203
\sub combinatorial interpretations, 358--360, 565,~568
\sub generalized, 361
\sub in sums, 181, 203, 317
\sub table of, 203
Cauchy, Augustin Louis, 607, 633
\v{C}ech, Eduard, vi
ceiling function, 67--69
\sub converted to floor, 68, 96
\sub graph of, 68
center of gravity, 273--274, 309
certificate of correctness, 104
Chace, Arnold Buffum, 608, 633
Chaimovich, Mark, 608
chain rule, 54, 483
change, 327--330, 374
\sub large amounts of, 344--346, 492
changing the index of summation, 30--31, 39
changing the tails of a sum, 466--469
cheating, viii, 195, 388, 401
\sub not, 158, 323
Chebyshev, Pafnuti{\u\i} L'vovich, 38, 145, 608, 633
\sub inequality, 390--391, 428, 430
\sub monotonic inequalities, 38, 576
cheese slicing, 19
Chen, Pang-Chieh, 632
Chinese Remainder Theorem, 126, 146
Chu Shih-Chieh [= Zh\=u Sh\`{\i}ji\'e], 169
Chung, Fan-Rong King, ix, 608, 635
Clausen, Thomas, 608, 634, 635
\sub product identities, 253
clearly, clarified, 417--418, 581
clich\'es, 166, 324, 357
closed form, 3, 7, 321
\sub for generating functions, 317
\sub not, 108, 573
\sub pretty good, 346
closed interval, 73--74
Cobb, Tyrus Raymond, 195
coefficient extraction, 197, 331
Cohen, Henri Jos\'e, 238
coins, 327--330
\sub biased, 401
\sub fair, 401, 430
\sub flipping, 401--410, 430--432, 437--438
\sub spinning, 401
Collingwood, Stuart Dodgson, 608
Collins, John, 624
Colombo, Cristoforo (= Columbus, Christopher), 74
coloring, 496
Columbia University, ix
combinations, 153
common logarithm, 449
commutative law, 30, 61, 64
\sub failure of, 322, 502, 551
\sub relaxed, 31
complete graph, 368
complex factorial powers, 211
complex numbers, 64
\sub roots of unity, 149, 204, 375, 553, 574, 598
composite numbers, 105, 518
composition of generating functions, 428
computer algebra, 42, 268, 501, 539
Comtet, Louis, 609, 636
Concrete Math Club, 74
concrete mathematics, defined, vi
conditional convergence, 59
conditional probability, 416--419, 424--425
confluent hypergeometric series, 206, 245
congruences, 123--126
Connection Machine, 131
contiguous hypergeometrics, 529
continuants, 301--309, 501
\sub and matrices, 318--319
\sub Euler's identity for, 303, 312
\sub zero parameters in, 314
continued fractions, 301, 304--309, 319
\sub large partial quotients of, 553, 563, 564, 602
convergence,
\sub absolute, 60--62, 64
\sub conditional, 59
\sub of power series, 206, 331, 451, 532
convex regions, 5, 20, 497
convolution, 197, 246, 333, 353--364
\sub binomial, 365, 367
\sub identities for, 202, 272, 373
\sub polynomials, 373
\sub Stirling, 272, 290
\sub Vandermonde, \see Vandermonde convolution
Conway, John Horton, 410, 609
cotangent function, 286, 317
counting,
\sub combinations, 153
\sub cycle arrangements, 259--262
\sub derangements, 193--196, 199--200
\sub integers in intervals, 73--74
\sub necklaces, 139--141
\sub parenthesized formulas, 357--359
\sub permutations, 111
\sub permutations by ascents, 267--268
\sub permutations by cycles, 262
\sub set partitions, 258--259
\sub spanning trees, 348--350, 356, 368--369, 374
\sub with generating functions, 320--330
coupon collecting, 583
Cover, Thomas Merrill, 636
Coxeter, Harold Scott Macdonald, 605
Cram\'er, Carl Harald, 525, 609, 634
Cray X-MP, 109
Crelle, August Leopold, 609, 633
cribbage, 65
Crispin, Mark Reed, 628
Crowe, Donald Warren, 609, 633
crudification, 447
Csirik, J\'anos Andr\'as, 590, 609
cubes, sum of consecutive, 51, 63, 283, 289, 367
cumulants, 397--401
\sub infinite, 576
\sub of binomial distribution, 432
\sub of discrete distribution, 438
\sub of Poisson distribution, 428--429
\sub third and fourth, 429, 579, 589
CUNY (= City University of New York), ix
Curtiss, David Raymond, 609, 634
cycles,
\sub de Bruijn, 500
\sub of beads, 139--140
\sub of permutations, 259--262
cyclic shift, 12