index.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\medskip
$i$, 22
implicit recurrences, 136--139, 193--195, 284
indefinite summation, 48--49
\sub by parts, 54--56
\sub of binomial coefficients, 161, 223--224, 246, 248, 313
\sub of hypergeometric terms, 224--229
independent random variables, 384, 427
\sub pairwise, 437
\sub products of, 386
\sub sums of, 386, 396--398
index set, 22, 30, 61
index variable, 22, 34, 60
induction, 3, 7, 10--11, 43
\sub backwards, 18
\sub basis of, 3, 320--321
\sub failure of, 17, 575
\sub important lesson about, 508, 549
inductive leap, 4, 43
infinite sums, 56--62, 64
\sub doubly, 59, 98, 482--483
information retrieval, 411--413
INT function, 67
insurance agents, 391
integer part, 70
integration, 45--46, 48
\sub by parts, 54, 472
\sub of generating functions, 333, 365
interchanging the order of summation, 34--41, 105, 136, 183, 185, 546
interpolation, 191--192
intervals, 73--74
invariant relation, 117
inverse modulo $m$, 125, 132, 147
inversion formulas, 193
\sub for binomial coefficients, 192--196
\sub for Stirling numbers, 264, 310
\sub for sums over divisors, 136--139
irrational numbers, 238
\sub continued fraction representations, 306
\sub rational approximations to, 122--123
\sub spectra of, 77, 96, 514
\sub Stern--Brocot representations, 122--123
Iverson, Kenneth Eugene, 24, 67, 618, 633
\sub convention, 24--25, 31, 34, 68, 75
\medskip
Jacobi, Carl Gustav Jacob, 64, 618
\sub polynomials, 543, 605
Janson, Carl Svante, 618
Jarden, Dov, 556, 618
Jeopardy, 361
joint distribution, 384
Jonassen, Arne Tormod, 618
Jones, Bush, 618
Josephus, Flavius, 8, 12, 19--20, 618
\sub numbers, 81, 97, 100
\sub problem, 8--17, 79--81, 95, 100, 144
\sub recurrence, generalized, 13--16, 79--81, 498
\sub subset, 20
Jouaillec, Louis Maurice, 632
Jungen, Reinwald, 618, 635
\medskip
$K$, \see continuants
Kafkaesque scenario, 274
Kaplansky, Irving, 8, 618
Karamata, Jovan, 257, 618
Karlin, Anna Rochelle, 632
Kauck\'y, Josef, 618, 635
Keiper, Jerry Bruce, 619
Kellogg, Oliver Dimon, 609
Kent, Clark (= Kal-El), 372
kernel functions, 370
Ketcham, Henry King, 148
kilometers, 301, 310, 550
Kilroy, James Joseph, vii
Kipling, Joseph Rudyard, 260
Kissinger, Henry Alfred, 379
Klamkin, Murray Seymour, 619, 633, 635
Klarner, David Anthony, 632
knockout tournament, 432--433
Knoebel, Robert Arthur, 619
Knopp, Konrad, 619, 636
Knuth, Donald Ervin, iii--vi, viii, ix, 102, 267, 411, 506, 553, 616, %
 618--620, 632, 633, 636,~\cpage
\sub numbers, 78, 97, 100
Knuth, John Martin, 636
Knuth, Nancy Jill Carter, ix
Kramp, Christian, 111, 620
Kronecker, Leopold, 521
\sub delta notation, 24
Kruk, John Martin, 519
Kummer, Ernst Eduard, 206, 529, 620--621, 634
\sub formula for hypergeometrics, 213, 217, 535
Kurshan, Robert Paul, 501, 621
\medskip
$L_n$, \see Lucas numbers
Lagny, Thomas Fantet de, 304, 621
Lagrange (= de la Grange), Joseph Louis, comte, 470, 621, 635
\sub identity, 64
Lah, Ivo, 621, 634
Lambert, Johann Heinrich, 201, 363, 613, 621
Landau, Edmund Georg Hermann, 443, 448, 621, 634, 636
Laplace, Pierre Simon, marquis de, 466, 606, 621
last but not least, 132, 469
Law of Large Numbers, 391
lcm, 103, \see least common multiple
leading coefficient, 235
least common multiple, 103, 107, 145
\sub of $\{1,\ldots,n\}$, 251, 319, 500
least integer function, \see ceiling function
least upper bound, 57, 61
LeChiffre, Mark Well, 148
left-to-right maxima, 316
Legendre, Adrien Marie, 621, 633
\sub polynomials, 543, 573, 575
Lehmer, Derrick Henry, 526, 622, 633, 635
Leibniz, Gottfried Wilhelm, Freiherr von, vii, 168, 616, 622
Lekkerkerker, Cornelius Gerrit, 622
Lengyel, Tam\'as L\'or\'ant, 622, 635
levels of problems, viii, 72--73, 95, 511
Levine, Eugene, 611, 635
lexicographic order, 441
lg: binary logarithm, 70
L'Hospital, Guillaume Fran\c{c}ois Antoine de, marquis de Sainte Mesme, %
  rule, 340, 396,~542
L\u{\i} Sh\`anl\'an R\'ensh\=u [= Qi\=ur\`en], 269, 622
Liang, Franklin Mark, 632
Lieb, Elliott Hershel, 622, 636
lies, and statistics, 195
Lincoln, Abraham, 401
linear difference operators, 240
lines in the plane, 4--8, 17, 19
Liouville, Joseph, 136--137, 622
little oh notation, 448
\sub considered harmful, 448--449
Littlewood, John Edensor, 239
ln: natural logarithm, 276
\sub discrete analog of, 53--54
\sub sum of, 481--482
log: common logarithm, 449
Logan, Benjamin Franklin (= Tex), Jr., 287, 622, 634--635
logarithmico-exponential functions, 442--443
logarithms, 449
\sub binary, 70
\sub discrete analog of, 53--54
\sub in $O$-notation, 449
\sub natural, 276
Long, Calvin Thomas, 622, 634
lottery, 387--388, 436--437
Lo\'u Sh\`{\i}t\=uo, 622
lower index of binomial coefficient, 154
\sub complex valued, 211
lower parameters of hypergeometric series, 205
Loyd, Samuel, 560, 622
Lucas, Fran\c cois \'Edouard Anatole, 1, 292, 622--623, 633--635
\sub numbers, 312, 316, 556
\L uczak, Tomasz Jan, 618
Lyness, Robert Cranston, 501, 623
\medskip
Maclaurin, Colin, 469, 623
MacMahon, Maj.~Percy Alexander, 140, 623
magic tricks, 293
Mallows, Colin Lingwood, 506
Markov, Andre{\u\i} Andreevich (the elder), processes, 405
Martian DNA, 377
Martzloff, Jean-Claude, 623
mathematical induction, 3, 7, 10--11, 43
\sub backwards, 18
\sub basis of, 3, 320--321
\sub failure of, 17, 575
\sub important lesson about, 508, 549
Mathews, Edwin Lee (= 41), "!Baseball" 8, 21, 94, 105, 106,~343
Mati{\t\i}asevich (= Matijasevich), \t{I}uri{\u\i} (= Yuri) Vladimirovich, %
 294, 623, 635
Mauldin, Richard Daniel, 611
Maxfield, Margaret Waugh, 630, 635
Mayr, Ernst, ix, 632, 633
McEliece, Robert James, 71
McGrath, James Patrick, 632
McKellar, Archie Charles, 614, 634
mean (average) of a probability distribution, 384--399
median, 384, 385, 437
mediant, 116
Melzak, Zdzislaw Alexander, vi, 623
Mendelsohn, Nathan Saul, 623, 634
Merchant, Arif Abdulhussein, 632
merging, 79, 175
Mersenne, Marin, 109--110, 131, 613, 623
\sub numbers, 109--110, 151, 292
\sub primes, 109--110, 127, 522--523
Mertens, Franz Carl Joseph, 139, 623
\sub constant, 23
miles, 301, 310, 550
Mills, Stella, 623
Mills, William Harold, 623, 634
minimum, 65, 249, 377
Mirsky, Leon, 635
mixture of probability distributions, 428
mnemonics, 74, 164
M\"obius, August Ferdinand, 136, 138, 623
\sub function, 136--139, 145, 149, 370--371, 462--463
mod: binary operation, 81--85
mod: congruence relation, 123--126
mod $0$, 82--83, 515
mode, 384, 385, 437
modular arithmetic, 123--129
modulus, 82
Moessner, Alfred, 624, 636
Moivre, Abraham de, 297, 481, 609
moments, 398--399
Montgomery, Hugh Lowell, 463, 624
Montgomery, Peter Lawrence, 624, 634
Moriarty, James, 162
Morse, Samuel Finley Breese, code, 302--303, 324,~551
Moser, Leo, 624, 633
Motzkin, Theodor Samuel, 556, 564, 618, 624
mountain ranges, 359, 565
mu function, \see M\"obius function
multinomial coefficients, 168, 171--172, 569
\sub recurrence for, 252
multinomial theorem, 149, 168
multiple of a number, 102
multiple sums, 34--41, 61; \also double sums
multiple-precision numbers, 127
multiplicative functions, 134--136, 144, 371
multisets, 77, 270
mumble function, 83, 84, 88, 507, 513
Murdock, Phoebe James, viii
Murphy's Law, 74
Myers, Basil Roland, 624, 635
\medskip
name and conquer, 2, 32, 88, 139
National Science Foundation, ix
natural logarithm, 53--54, 276, 481--482
Naval Research, ix
Navel research, 299
nearest integer, 95
\sub rounding to, 195, 300, 344, 491
\sub unbiased, 507
necessary and sufficient conditions, 72
necklaces, 139--141, 259
negating the upper index, 164--165
negative binomial distribution, 402--403, 428
negative factorial powers, 52, 63, 188
Newman, James Roy, 630
Newman, Morris, 635
Newton, Sir Isaac, 189, 277, 624
\sub series, 189--192
Newtonian generating function, 378
Niven, Ivan Morton, 332, 624, 633
nonprime numbers, 105, 518
nontransitive paradox, 410
normal distribution, 438
notation, x--xi, 2, 637
\sub extension of, 49, 52, 154, 210--211, 266, 271, 311, 319
\sub ghastly, 67, 175
\sub need for new, 83, 115, 267
nu function: sum of digits,
\sub binary (radix $2$), 12, 114, 250, 525, 557
\sub other radices, 146, 525, 552
null case,
\sub for spanning trees, 349, 565
\sub for Stirling numbers, 258
\sub for tilings, 320--321
\sub for Tower of Hanoi, 2
number system, 107, 119
\sub binomial, 245
\sub Fibonacci, 296--297, 301, 307, 310, 318
\sub prime-exponent, 107, 116
\sub radix, \see radix notation
\sub residue, 126--129, 144
\sub Stern--Brocot, \see Stern--Brocot number system
number theory, 102--152
\medskip
$o$, considered harmful, 448--449
$O$-notation, 76, 443--449
\sub abuse of, 447--448, 489
\sub one-way equalities with, 446--447, 489--490
obvious, clarified, 417, 526
odds, 410
Odlyzko, Andrew Michael, 81, 564, 590, 616, 624, 636
Office of Naval Research, ix
one-way equalities, 446--447, 489--490
open interval, 73--74, 96
operators, 47
\sub anti-derivative ($\int$), 48
\sub anti-difference ($\sum$), 48
\sub derivative ($D$), 47, 310
\sub difference ($\Delta$), 47
\sub equations of, 188, 191, 241, 310, 471
\sub shift ($E$, $K$, $N$), 55, 240
\sub theta ($\vartheta$), 219, 310
optical illusions, 292, 293, 560
organ-pipe order, 524
Oz, Wizard of, 581
\medskip
Pacioli, Luca, 614
Palais, Richard Sheldon, viii
paradoxes,
\sub chessboard, 293, 317
\sub coin flipping, 408--410
\sub pair of boxes, 531, 535, 539
paradoxical sums, 57
parallel summation, 159, 174, 208--210
parentheses, 357--359
parenthesis conventions, xi
partial fraction expansions, 298--299, 338--341
\sub for easy summation and differentiation, 64, 376, 476, 504, 586
\sub not always easiest, 374
\sub of $1/x{x+n\choose n}$, 189
\sub of $1/(z^n-1)$, 558
\sub powers of, 246, 376
partial quotients, 306
\sub and discrepancies, 319, 598--599, 602
\sub large, 553, 563, 564, 602
partial sums, \see indefinite summation
\sub required to be positive, 359--362
partition into nearly equal parts, 83--85
partitions, of the integers, 77--78, 96, 99, 101
\sub of a number, 330, 377
\sub of a set, 258--259, 373
Pascal, Blaise, 155, 156, 624, 633
Pascal's triangle, 155
\sub extended upward, 164
\sub hexagon property, 155--156, 242, 251
\sub row lcms, 251
\sub row products, 243
\sub row sums, 163, 165--166
\sub variant of, 250
Patashnik, Amy Markowitz, ix
Patashnik, Oren, iii, iv, vi, ix, 102, 506, 616, 632
Patil, Ganapati Parashuram, 624, 636
Paule, Peter, 537, 546
Peirce, Charles Santiago Sanders, 525, 624--625, 634
\sub sequence, 151
Penney, Walter Francis, 408, 625
Penney ante, 408--410, 430, 437, 438
pentagon, 314~(exercise~46), 430, 434
pentagonal numbers, 380
Percus, Jerome Kenneth, 625, 636
perfect powers, 66
periodic recurrences, 20, 179, 498
permutations, 111--112
\sub ascents in, 267--268, 270
\sub cycles in, 259--262
\sub excedances in, 314
\sub fixed points in, 193--196, 393--394, 400--401, 418
\sub left-to-right maxima in, 314
\sub random, 393--394, 400--401, 428
\sub up-down, 377
\sub without fixed points, \see derangements
personal computer, 109
perspiration, 234--235
perturbation method, 32--33, 43--44, 64, 179, 284--285
Petkov\v{s}ek, Marko, 229, 575, 625, 634
Pfaff, Johann Friedrich, 207, 214, 217, 529, 625, 634
\sub reflection law, 217, 247, 539
pgf: probability generating function, 394
phages, 434, 438
phi ($\approx1.61803$), 299--301
\sub as canonical constant, 70
\sub continued fraction for, 310
\sub in fifth roots of unity, 553
\sub in solutions to recurrences, 97, 99, 285--286
\sub Stern--Brocot representation of, 550
phi function, 133--135
\sub dgf for, 371
\sub divisibility by, 151
Phi function: sum of $\phi$, 137--139, 462--463
Phidias, 299
philosophy, vii, 11, 16, 46, 71, 72, 75, 91, 170, 181, 194, 331, 467, 503, %
 508, 603
phyllotaxis, 291
pi ($\approx3.14159$, 26, 286
\sub as canonical constant, 70, 416, 423
\sub large partial quotients of, 564
\sub Stern--Brocot representation of, 146
pi function, 110--111, 452, 593
\sub preposterous expressions for, 516
Pig, Porky, 496
pigeonhole principle, 130
Pincherle, Salvatore, 617
Pisano, Leonardo, 613, \see Fibonacci
Pittel, Boris Gershon, 576, 618
pizza, 4, 423
planes, cutting, 19
pneumathics, 164
Pochhammer, Leo, 48, 625
\sub symbol, 48
pocket calculators, 67, 77, 459
\sub failure of, 344
Poincar\'e, Jules Henri, 625, 636
Poisson, Sim\'eon Denis, 471, 625
\sub distribution, 428--429, 579
\sub summation formula, 602
Pollak, Henry Otto, 616, 633
P\'olya, George (= Gy\"orgy), vi, 16, 327, 508, 625, 633, 635, 636
polygons,
\sub dissection of, 379
\sub triangulation of, 374
\sub Venn diagrams with, 20
polynomial argument, 158, 163
\sub for rational functions, 527
\sub opposite of, 210
polynomially recursive sequence, 374
polynomials, 189
\sub Bernoulli, 367--368, 470--475
\sub continuant, 301--309
\sub convolution, 373
\sub cyclotomic, 149
\sub degree of, 158, 226
\sub divisibility of, 225
\sub Euler, 574
\sub Jacobi, 543, 605
\sub Legendre, 543, 573, 575
\sub Newton series for, 189--191
\sub reflected, 339
\sub Stirling, 271--272, 290, 311, 317, 352
Poonen, Bjorn, 501, 633
Porter, Thomas K, 632
Portland cement, \see concrete (in another book)
power series, 196, \see generating functions
\sub formal, 206, 331, 348, 532
Pr, 381--382
Pratt, Vaughan Ronald, 632
preferential arrangements, 378~(exercise~44)
primality testing, 110, 148
\sub impractical method, 133
prime algebraic integers, 106, 147
prime numbers, 105--111
\sub gaps between, 150--151, 525
\sub largest known, 109--110
\sub Mersenne, 109--110, 127, 522
\sub size of $n$th, 110--111, 456--457
\sub sum of reciprocals, 22--25
prime to, 115
prime-exponent representation, 107, 116
Princeton University, ix, 427
probabilistic analysis of an algorithm, 413--426
probability, 195, 381--438
\sub conditional, 416--419, 424--425
\sub discrete, 381--438
\sub generating functions, 394--401
\sub spaces, 381
probability distributions, 367
\sub binomial, 401--402, 415, 428, 432
\sub composition or mixture of, 428
\sub joint, 384
\sub negative binomial, 402--403, 428
\sub normal, 438
\sub Poisson, 428--429, 579
\sub uniform, 395--396, 420--421
problems, levels of, viii, 72--73, 95, 511
product notation, 64, 106
product of consecutive odd numbers, 186, 270
progression, \see arithmetic progression, geometric progression
proof, 4, 7
proper terms, 239--241, 255--256
properties, 23, 34, 72--73
prove or disprove, 71--72
psi function, 551
pulling out the large part, 453, 458
puns, ix, 220
Pythagoras of Samos, theorem, 510
\medskip
quadratic domain, 147
quicksort, 28--29, 54
quotation marks, xi
quotient, 81
\medskip
rabbits, 310
radix notation, 11--13, 15--16, 109, 195, 526
\sub length of, 70, 460
\sub related to prime factors, 113--114, 146--148, 245
Rado, Richard, 625, 635
Rahman, Mizanur, 223, 614
Rainville, Earl David, 529, 626