PREFACE ix or chalk.(For example,one of the trademarks of the new design is the symbol for zero,0',which is slightly pointed at the top because a handwritten zero I'm unaccustomed rarely closes together smoothly when the curve returns to its starting point.) to this face. The letters are upright,not italic,so that subscripts,superscripts,and ac- cents are more easily fitted with ordinary symbols.This new type family has been named AMS Euler,after the great Swiss mathematician Leonhard Euler (1707-1783)who discovered so much of mathematics as we know it today. The alphabets include Euler Text(Aa Bb Cc through Xx Yy Zz),Euler Frak- tur (a Bb Cc through 33),and Euler Script Capitals (AB C through X yZ),as well as Euler Greek (Aa BB Ty through XxY Qw)and special symbols such as and We are especially pleased to be able to inaugurate the Euler family of typefaces in this book,because Leonhard Euler's spirit truly lives on every page:Concrete mathematics is Eulerian mathematics. Dear prof:Thanks The authors are extremely grateful to Andrei Broder,Ernst Mayr,An- for (n)the puns, drew Yao,and Frances Yao,who contributed greatly to this book during the (2)the subject matter. years that they taught Concrete Mathematics at Stanford.Furthermore we offer 1024 thanks to the teaching assistants who creatively transcribed what took place in class each year and who helped to design the examination ques- tions;their names are listed in Appendix C.This book,which is essentially a compendium of sixteen years'worth of lecture notes,would have been im- possible without their first-rate work. Many other people have helped to make this book a reality.For example, don't see how we wish to commend the students at Brown,Columbia,CUNY,Princeton, what I've learned Rice,and Stanford who contributed the choice graffiti and helped to debug will ever help me. our first drafts.Our contacts at Addison-Wesley were especially efficient and helpful;in particular,we wish to thank our publisher (Peter Gordon), production supervisor(Bette Aaronson),designer(Roy Brown),and copy ed- itor (Lyn Dupre).The National Science Foundation and the Office of Naval Research have given invaluable support.Cheryl Graham was tremendously helpful as we prepared the index.And above all,we wish to thank our wives I bad a lot of trou- (Fan,Jill,and Amy)for their patience,support,encouragement,and ideas. ble in this class,but We have tried to produce a perfect book,but we are imperfect authors. I know it sharpened my math skills and Therefore we solicit help in correcting any mistakes that we've made.A re- my thinking skills. ward of $2.56 will gratefully be paid to the first finder of any error,whether it is mathematical,historical,or typographical. Murray Hill,New Jersey -RLG and Stanford,California DEK I would advise the May 1988 OP casual student to stay away from this course
I’m unaccustomed to this face. Dear prof: Thanks for (1) the puns, (2) the subject matter. 1 don’t see how what I’ve learned will ever help me. I bad a lot of trouble in this class, but I know it sharpened my math skills and my thinking skills. 1 would advise the casual student to stay away from this course. PREFACE ix or chalk. (For example, one of the trademarks of the new design is the symbol for zero, ‘0’, which is slightly pointed at the top because a handwritten zero rarely closes together smoothly when the curve returns to its starting point.) The letters are upright, not italic, so that subscripts, superscripts, and accents are more easily fitted with ordinary symbols. This new type family has been named AM.9 Euler, after the great Swiss mathematician Leonhard Euler (1707-1783) who discovered so much of mathematics as we know it today. The alphabets include Euler Text (Aa Bb Cc through Xx Yy Zz), Euler Fraktur (%a23236 cc through Q’$lu 3,3), and Euler Script Capitals (A’B e through X y Z), as well as Euler Greek (AOL B fi ry through XXY’J, nw) and special symbols such as p and K. We are especially pleased to be able to inaugurate the Euler family of typefaces in this book, because Leonhard Euler’s spirit truly lives on every page: Concrete mathematics is Eulerian mathematics. The authors are extremely grateful to Andrei Broder, Ernst Mayr, Andrew Yao, and Frances Yao, who contributed greatly to this book during the years that they taught Concrete Mathematics at Stanford. Furthermore we offer 1024 thanks to the teaching assistants who creatively transcribed what took place in class each year and who helped to design the examination questions; their names are listed in Appendix C. This book, which is essentially a compendium of sixteen years’ worth of lecture notes, would have been impossible without their first-rate work. Many other people have helped to make this book a reality. For example, we wish to commend the students at Brown, Columbia, CUNY, Princeton, Rice, and Stanford who contributed the choice graffiti and helped to debug our first drafts. Our contacts at Addison-Wesley were especially efficient and helpful; in particular, we wish to thank our publisher (Peter Gordon), production supervisor (Bette Aaronson), designer (Roy Brown), and copy editor (Lyn Dupre). The National Science Foundation and the Office of Naval Research have given invaluable support. Cheryl Graham was tremendously helpful as we prepared the index. And above all, we wish to thank our wives (Fan, Jill, and Amy) for their patience, support, encouragement, and ideas. We have tried to produce a perfect book, but we are imperfect authors. Therefore we solicit help in correcting any mistakes that we’ve made. A reward of $2.56 will gratefully be paid to the first finder of any error, whether it is mathematical, historical, or typographical. Murray Hill, New Jersey -RLG and Stanford, California DEK May 1988 OP
A Note on Notation SOME OF THE SYMBOLISM in this book has not (yet?)become standard Here is a list of notations that might be unfamiliar to readers who have learned similar material from other books,together with the page numbers where these notations are explained: Notation Name Page Inx natural logarithm:log,x 262 lgx binary logarithm:log,x 70 log x common logarithm:log,ox 435 floor:maxn n x,integer n) 67 [x] ceiling:min nn >x,integer n 67 xmody remainder:x-y x/y] 82 (x) fractional part:x mod 1 ∑fixx indefinite summation 48 ∑8fKx definite summation 49 x falling factorial power:x!/(x-n)! 47 xii rising factorial power:(x +n)/T(x) 48 nj subfactorial:n!/0!-n!/1!+..+(-1 )"n!/n! 194 Rz real part:x,if z =x iy 64 If you don't under- Jz imaginary part:y,if z=x+iy 64 stand what the x denotes at the Hn harmonic number:1 /1+...+1 /n 29 bottom of this page, try asking your H generalized harmonic number.1 /1x +..+1 /nx 263 Latin professor instead of your f“( mth derivative of f at z 456 math professor
A Note on Notation SOME OF THE SYMBOLISM in this book has not (yet?) become standard. Here is a list of notations that might be unfamiliar to readers who have learned similar material from other books, together with the page numbers where these notations are explained: Notation lnx kx log x 1x1 1x1 xmody {xl x f(x) 6x x: f(x) 6x XI1 X ii ni iRz Jz H, H’X’ n f'"'(z) X Name natural logarithm: log, x binary logarithm: log, x common logarithm: log, 0 x floor: max{n 1 n < x, integer n} ceiling: min{ n 1 n 3 x, integer n} remainder: x - y lx/y] fractional part: x mod 1 indefinite summation Page 262 70 435 67 67 82 70 48 definite summation 49 falling factorial power: x!/(x - n)! rising factorial power: T(x + n)/(x) subfactorial: n!/O! - n!/l ! + . . + (-1 )“n!/n! real part: x, if 2 = x + iy imaginary part: y, if 2 = x + iy harmonic number: 1 /l + . . . + 1 /n generalized harmonic number: 1 /lx + . . . + 1 /nx mth derivative of f at z 47 48 194 64 64 2 9 263 456 If you don’t understand what the x denotes at the bottom of this page, try asking your Latin professor instead of your math professor
A NOTE ON NOTATION xi R Stirling cycle number (the "first kind") 245 Stirling subset number (the "second kind") 244 n Eulerian number 253 0m n Prestressed concrete Second-order Eulerian number 256 mathematics is con- m/∥ crete mathematics that's preceded by (am...ao)b radix notation for ∑oakb水 11 a bewildering list of notations. K(a1,.,an) continuant polynomial 288 (1习 hypergeometric function 205 #A cardinality:number of elements in the set A 39 [z"]f(z) coefficient of z in f (z) 197 [c.] closed interval:the set{x≤x≤y 73 [m=n] 1 if m n,otherwise 0* 24 [m\n] 1 if m divides n,otherwise 0* 102 [m\n] 1 if m exactly divides n,otherwise 0* 146 m⊥n 1 if m is relatively prime to n,otherwise 0* 115 *In general,if S is any statement that can be true or false,the bracketed notation [S]stands for 1 if S is true,0 otherwise. Throughout this text,we use single-quote marks(...')to delimit text as it is written,double-quote marks ("..")for a phrase as it is spoken.Thus, Also‘nonstring'is the string of letters 'string'is sometimes called a "string!' a string An expression of the form 'a/bc'means the same as 'a/(bc)'.Moreover, logx/logy (logx)/(logy)and 2n!=2(n!)
n [ 1n-l n {Im n 0 m n Prestressed concrete mathematics is con- (i m >> Crete mathematics that’s preceded by (‘h...%)b a bewildering list of notations. K(al,. . . ,a,) F #A iz”l f(z) la..@1 [m=nl [m\nl Im\nl [m-l-n1 A NOTE ON NOTATION xi Stirling cycle number (the “first kind”) 245 Stirling subset number (the “second kind”) 244 Eulerian number 253 Second-order Eulerian number 256 radix notation for z,“=, akbk 11 continuant polynomial 288 hypergeometric function 205 cardinality: number of elements in the set A 39 coefficient of zn in f (2) 197 closed interval: the set {x 1016 x 6 (3} 73 1 if m = n, otherwise 0 * 24 1 if m divides n, otherwise 0 * 102 1 if m exactly divides n, otherwise 0 * 146 1 if m is relatively prime to n, otherwise 0 * 115 *In general, if S is any statement that can be true or false, the bracketed notation [S] stands for 1 if S is true, 0 otherwise. Throughout this text, we use single-quote marks (‘. . . ‘) to delimit text as it is written, double-quote marks (“. . “ ) for a phrase as it is spoken. Thus, Also ‘nonstring’ is the string of letters ‘string’ is sometimes called a “string!’ a string. An expression of the form ‘a/be’ means the same as ‘a/(bc)‘. Moreover, logx/logy = (logx)/(logy) and 2n! = 2(n!)
Contents 1 Recurrent Problems 1 1.1 The Tower of Hanoi I 1.2 Lines in the Plane 4 1.3 The Josephus Problem 8 Exercises 17 2 Sums 21 2.1 Notation 21 2.2 Sums and Recurrences 25 2.3 Manipulation of Sums 30 2.4 Multiple Sums 34 2.5 General Methods 41 2.6 Finite and Infinite Calculus 47 2.7 Infinite Sums 56 Exercises 62 3 Integer Functions 67 3.1 Floors and Ceilings 67 3.2 Floor/Ceiling Applications 70 3.3 Floor/Ceiling Recurrences 78 3.4 'mod':The Binary Operation 81 3.5 Floor/Ceiling Sums 86 Exercises 95 4 Number Theory 102 4.1 Divisibility 102 4.2 Primes 105 4.3 Prime Examples 107 4.4 Factorial Factors 111 4.5 Relative Primality 115 4.6‘mod':The Congruence Relation 123 4.7 Independent Residues 126 4.8 Additional Applications 129 4.9 Phi and Mu 133 Exercises 144 5 Binomial Coefficients 153 5.1 Basic Identities 153 5.2 Basic Practice 172 xii
Contents 1 Recurrent Problems 1 1.1 The Tower of Hanoi 1 1.2 Lines in the Plane 4 1.3 The Josephus Problem 8 Exercises 17 2 Sums 2.1 Notation 21 2.2 Sums and Recurrences 25 2.3 Manipulation of Sums 30 2.4 Multiple Sums 34 2.5 General Methods 41 2.6 Finite and Infinite Calculus 47 2.7 Infinite Sums 56 Exercises 62 21 3 Integer Functions 67 3.1 Floors and Ceilings 67 3.2 Floor/Ceiling Applications 70 3.3 Floor/Ceiling Recurrences 78 3.4 ‘mod’: The Binary Operation 81 3.5 Floor/Ceiling Sums 86 Exercises 95 4 Number Theory 102 4.1 Divisibility 102 4.2 Primes 105 4.3 Prime Examples 107 4.4 Factorial Factors 111 4.5 Relative Primality 115 4.6 ‘mod’: The Congruence Relation 123 4.7 Independent Residues 126 4.8 Additional Applications 129 4.9 Phi and Mu 133 Exercises 144 5 Binomial Coefficients 153 5.1 Basic Identities 153 5.2 Basic Practice 172 xii
CONTENTS xiii 5.3 Tricks of the Trade 186 5.4 Generating Functions 196 5.5 Hypergeometric Functions 204 5.6 Hypergeometric Transformations 216 5.7 Partial Hypergeometric Sums 223 Exercises 230 6 Special Numbers 243 6.1 Stirling Numbers 243 6.2 Eulerian Numbers 253 6.3 Harmonic Numbers 258 6.4 Harmonic Summation 265 6.5 Bernoulli Numbers 269 6.6 Fibonacci Numbers 276 6.7 Continuants 287 Exercises 295 7 Generating Functions 306 7.1 Domino Theory and Change 306 7.2 Basic Maneuvers 317 7.3 Solving Recurrences 323 7.4 Special Generating Functions 336 7.5 Convolutions 339 7.6 Exponential Generating Functions 350 7.7 Dirichlet Generating Functions 356 Exercises 357 8 Discrete Probability 367 8.1 Definitions 367 8.2 Mean and Variance 373 8.3 Probability Generating Functions 380 8.4 Flipping Coins 387 8.5 Hashing 397 Exercises 413 9 Asymptotics 425 9.1 A Hierarchy 426 9.2 0 Notation 429 9.3 0 Manipulation 436 9.4 Two Asymptotic Tricks 449 9.5 Euler's Summation Formula 455 9.6 Final Summations 462 Exercises 475 A Answers to Exercises 483 B Bibliography 578 C Credits for Exercises 601 Index 606 List of Tables 624
CONTENTS xiii 5.3 Tricks of the Trade 186 5.4 Generating Functions 196 5.5 Hypergeometric Functions 204 5.6 Hypergeometric Transformations 216 5.7 Partial Hypergeometric Sums 223 Exercises 230 6 Special Numbers 243 6.1 Stirling Numbers 243 6.2 Eulerian Numbers 253 6.3 Harmonic Numbers 258 6.4 Harmonic Summation 265 6.5 Bernoulli Numbers 269 6.6 Fibonacci Numbers 276 6.7 Continuants 287 Exercises 295 7 Generating Functions 306 7.1 Domino Theory and Change 306 7.2 Basic Maneuvers 317 7.3 Solving Recurrences 323 7.4 Special Generating Functions 336 7.5 Convolutions 339 7.6 Exponential Generating Functions 350 7.7 Dirichlet Generating Functions 356 Exercises 357 8 Discrete Probability 367 8.1 Definitions 367 8.2 Mean and Variance 373 8.3 Probability Generating Functions 380 8.4 Flipping Coins 387 8.5 Hashing 397 Exercises 413 9 Asymptotics 425 9.1 A Hierarchy 426 9.2 0 Notation 429 9.3 0 Manipulation 436 9.4 Two Asymptotic Tricks 449 9.5 Euler’s Summation Formula 455 9.6 Final Summations 462 Exercises 475 A Answers to Exercises 483 B Bibliography 578 C Credits for Exercises 601 Index 606 List of Tables 624