INDEX906
generating function, 647, 654
Generating Functions, 627
generating functions, 502
geometric distribution, 757 , 757
geometric series, 627
geometric sum, 503
Godel, Kurt, 223 ̈
going broke, 839
Goldbach’s Conjecture,see alsoprime,
7 , 58, 255
golden ratio, 250, 287
good count, 199 , 657, 658
Google, 839
graph
bipartite, 401
coloring problem, 414
diameter, 374
matching, 404
perfect, 404
valid coloring, 414
width, 451, 452
graph coloring, 414
gray edge, 430
greatest common divisor, 243, 248
guess-and-verify, 865
half-adder, 63
Hall’s Matching Theorem, 402
Hall’s Theorem, 405, 610
Hall’s theorem, 442
Halting Problem, 215
Hamiltonian Cycle Problem, 459
Handshaking Lemma, 397
Hardy, G. H., 243
harmonic number, 519
harmonic numbers, 526
Hat-Check problem, 791
homogeneous linear recurrence, 875
homogeneous solution, 879
hypercube, 459
identity relation, 327 , 338, 363, 364,
368
image, 88, 92
inverse image, 92
implication, 11, 13, 43
false hypothesis, 44
Inclusion-Exclusion, 582, 584
inclusion-exclusion for probabilities,
687
Inclusion-Exclusion Rule, 582
incompleteness theorem, 223
independence, 714
independent, 799
independent random variables, 741
indicator random variable, 740
indicator variable, 752, 797, 821
indicator variables, 742
indirect proof, seeproof by contra-
diction
induction, 116 , 129, 188
induciton hypothesis, 118
inductive step, 118
structural induction, 173, 175
inference rules, 10
infinity,seecountable, Mapping Rules,
set, set theory
inhomogeneous linear recurrence, 879
injection,seebinary relation
Integral Method, 537
intended profit, 839
interest rate, 536
intersection, 83
invariant, 130, 131, 135 , 246
Invariant Principle, 135
inverse (multiplicative), 270
irreducible, 292
irreflexive relation, 336, 343 , 363
isomorphic, 339 , 362, 496k-combination,seeSbset Split Theo-