CONCRETE MATHEMATICS Ronald L.Graham AT&T Bell Laboratories Donald E.Knuth Stanford University Oren Patashnik Stanford University ADDISON-WESLEY PUBLISHING COMPANY Reading.Massachusetts Menlo Park.California New York Don Mills,Ontario Wokingham,England Amsterdam Bonn Sydney Singapore Tokyo Madrid San Juan
CONCRETE MATHEMATICS Ronald L. Graham AT&T Bell Laboratories Donald E. Knuth Stanford University Oren Patashnik Stanford University A ADDISON-WESLEY PUBLISHING COMPANY Reading, Massachusetts Menlo Park, California New York Don Mills, Ontario Wokingham, England Amsterdam Bonn Sydney Singapore Tokyo Madrid San Juan
Preface “A odience,level, THIS BOOK IS BASED on a course of the same name that has been taught and treatment annually at Stanford University since 1970.About fifty students have taken it a description of such matters is each year-juniors and seniors,but mostly graduate students-and alumni what prefaces are of these classes have begun to spawn similar courses elsewhere.Thus the time supposed to be seems ripe to present the material to a wider audience (including sophomores). about.” -P.R.Halmos (142] It was a dark and stormy decade when Concrete Mathematics was born. Long-held values were constantly being questioned during those turbulent years;college campuses were hotbeds of controversy.The college curriculum itself was challenged,and mathematics did not escape scrutiny.John Ham- mersley had just written a thought-provoking article "On the enfeeblement of mathematical skills by 'Modern Mathematics'and by similar soft intellectual trash in schools and universities"[145];other worried mathematicians [272] “People do acquire even asked,"Can mathematics be saved?"One of the present authors had a little brief author- embarked on a series of books called The Art of Computer Programming,and ity by equpping themselves with in writing the first volume he (DEK)had found that there were mathematical jargon:they can tools missing from his repertoire;the mathematics he needed for a thorough, pontificate and aira well-grounded understanding of computer programs was quite different from superficial expertise. But what we should what he'd learned as a mathematics major in college.So he introduced a new ask of educated course,teaching what he wished somebody had taught him. mathematicians is The course title "Concrete Mathematics"was originally intended as an not what they can antidote to "Abstract Mathematics,"since concrete classical results were rap- speecltify about, mor eoen what they idly being swept out of the modern mathematical curriculum by a new wave know about the of abstract ideas popularly called the "New Math!'Abstract mathematics is a existing corpus of mathematical wonderful subject,and there's nothing wrong with it:It's beautiful,general, knowledge.but and useful.But its adherents had become deluded that the rest of mathemat- rather what can ics was inferior and no longer worthy of attention.The goal of generalization they now do with had become so fashionable that a generation of mathematicians had become their leaming and whether they cn unable to relish beauty in the particular,to enjoy the challenge of solving actually solve math- quantitative problems,or to appreciate the value of technique.Abstract math- ematical problems ematics was becoming inbred and losing touch with reality;mathematical ed- arising in practice. ucation needed a concrete counterweight in order to restore a healthy balance In short,we look for deeds not words." When DEK taught Concrete Mathematics at Stanford for the first time, -J.Hammersley (145] he explained the somewhat strange title by saying that it was his attempt
Preface “A odience, level, and treatment - a description of such matters is what prefaces are supposed to be about.” - P. R. Halmos 11421 “People do acquire a little brief authority by equipping themselves with jargon: they can pontificate and air a superficial expertise. But what we should ask of educated mathematicians is not what they can speechify about, nor even what they know about the existing corpus of mathematical knowledge, but rather what can they now do with their learning and whether they can actually solve mathematical problems arising in practice. In short, we look for deeds not words.” -J. Hammersley [145] THIS BOOK IS BASED on a course of the same name that has been taught annually at Stanford University since 1970. About fifty students have taken it each year-juniors and seniors, but mostly graduate students-and alumni of these classes have begun to spawn similar courses elsewhere. Thus the time seems ripe to present the material to a wider audience (including sophomores). It was a dark and stormy decade when Concrete Mathematics was born. Long-held values were constantly being questioned during those turbulent years; college campuses were hotbeds of controversy. The college curriculum itself was challenged, and mathematics did not escape scrutiny. John Hammersley had just written a thought-provoking article “On the enfeeblement of mathematical skills by ‘Modern Mathematics’ and by similar soft intellectual trash in schools and universities” [145]; other worried mathematicians [272] even asked, “Can mathematics be saved?” One of the present authors had embarked on a series of books called The Art of Computer Programming, and in writing the first volume he (DEK) had found that there were mathematical tools missing from his repertoire; the mathematics he needed for a thorough, well-grounded understanding of computer programs was quite different from what he’d learned as a mathematics major in college. So he introduced a new course, teaching what he wished somebody had taught him. The course title “Concrete Mathematics” was originally intended as an antidote to “Abstract Mathematics,” since concrete classical results were rapidly being swept out of the modern mathematical curriculum by a new wave of abstract ideas popularly called the “New Math!’ Abstract mathematics is a wonderful subject, and there’s nothing wrong with it: It’s beautiful, general, and useful. But its adherents had become deluded that the rest of mathematics was inferior and no longer worthy of attention. The goal of generalization had become so fashionable that a generation of mathematicians had become unable to relish beauty in the particular, to enjoy the challenge of solving quantitative problems, or to appreciate the value of technique. Abstract mathematics was becoming inbred and losing touch with reality; mathematical education needed a concrete counterweight in order to restore a healthy balance. When DEK taught Concrete Mathematics at Stanford for the first time, he explained the somewhat strange title by saying that it was his attempt V
vi PREFACE to teach a math course that was hard instead of soft.He announced that, contrary to the expectations of some of his colleagues,he was not going to teach the Theory of Aggregates,nor Stone's Embedding Theorem,nor even the Stone-Tech compactification.(Several students from the civil engineering “The heart of math- department got up and quietly left the room.) ematics consists Although Concrete Mathematics began as a reaction against other trends, of concrete exam- ples and concrete the main reasons for its existence were positive instead of negative.And as problems." the course continued its popular place in the curriculum,its subject matter -P.R.Halmos [141] "solidified"and proved to be valuable in a variety of new applications.Mean- while,independent confirmation for the appropriateness of the name came from another direction,when Z.A.Melzak published two volumes entitled "It is downright Companion to Concrete Mathematics 214. sinful to teach the abstract before the The material of concrete mathematics may seem at first to be a disparate concrete. bag of tricks,but practice makes it into a disciplined set of tools.Indeed,the -Z.A.Melzak (214 techniques have an underlying unity and a strong appeal for many people. When another one of the authors (RLG)first taught the course in 1979,the students had such fun that they decided to hold a class reunion a year later. But what exactly is Concrete Mathematics?It is a blend of CONtinuous Concrete Ma the- and discRETE mathematics.More concretely,it is the controlled manipulation matics is a bridge to abstract mathe- of mathematical formulas,using a collection of techniques for solving prob- matics. lems.Once you,the reader,have learned the material in this book,all you will need is a cool head,a large sheet of paper,and fairly decent handwriting in order to evaluate horrendous-looking sums,to solve complex recurrence relations,and to discover subtle patterns in data.You will be so fluent in algebraic techniques that you will often find it easier to obtain exact results than to settle for approximate answers that are valid only in a limiting sense. The major topics treated in this book include sums,recurrences,ele- "The advanced mentary number theory,binomial coefficients,generating functions,discrete reader who skips probability,and asymptotic methods.The emphasis is on manipulative tech- parts that appear too elementary ny nique rather than on existence theorems or combinatorial reasoning;the goal miss more than is for each reader to become as familiar with discrete operations (like the the less advanced greatest-integer function and finite summation)as a student of calculus is reader who skips parts that appear familiar with continuous operations (like the absolute-value function and in- too complex..刀 finite integration). -G.P6lya [238] Notice that this list of topics is quite different from what is usually taught nowadays in undergraduate courses entitled "Discrete Mathematics!'There- fore the subject needs a distinctive name,and "Concrete Mathematics"has proved to be as suitable as any other. (We're not bold The original textbook for Stanford's course on concrete mathematics was enough to try Distinuous Math- the "Mathematical Preliminaries"section in The Art of Computer Program- ema tics.) ming [173.But the presentation in those 110 pages is quite terse,so another author(OP)was inspired to draft a lengthy set of supplementary notes.The
vi PREFACE to teach a math course that was hard instead of soft. He announced that, contrary to the expectations of some of his colleagues, he was not going to teach the Theory of Aggregates, nor Stone’s Embedding Theorem, nor even the Stone-Tech compactification. (Several students from the civil engineering department got up and quietly left the room.) Although Concrete Mathematics began as a reaction against other trends, the main reasons for its existence were positive instead of negative. And as the course continued its popular place in the curriculum, its subject matter “solidified” and proved to be valuable in a variety of new applications. Meanwhile, independent confirmation for the appropriateness of the name came from another direction, when Z. A. Melzak published two volumes entitled Companion to Concrete Mathematics [214]. The material of concrete mathematics may seem at first to be a disparate bag of tricks, but practice makes it into a disciplined set of tools. Indeed, the techniques have an underlying unity and a strong appeal for many people. When another one of the authors (RLG) first taught the course in 1979, the students had such fun that they decided to hold a class reunion a year later. But what exactly is Concrete Mathematics? It is a blend of continuous and diSCRETE mathematics. More concretely, it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems. Once you, the reader, have learned the material in this book, all you will need is a cool head, a large sheet of paper, and fairly decent handwriting in order to evaluate horrendous-looking sums, to solve complex recurrence relations, and to discover subtle patterns in data. You will be so fluent in algebraic techniques that you will often find it easier to obtain exact results than to settle for approximate answers that are valid only in a limiting sense. The major topics treated in this book include sums, recurrences, elementary number theory, binomial coefficients, generating functions, discrete probability, and asymptotic methods. The emphasis is on manipulative technique rather than on existence theorems or combinatorial reasoning; the goal is for each reader to become as familiar with discrete operations (like the greatest-integer function and finite summation) as a student of calculus is familiar with continuous operations (like the absolute-value function and infinite integration). Notice that this list of topics is quite different from what is usually taught nowadays in undergraduate courses entitled “Discrete Mathematics!’ Therefore the subject needs a distinctive name, and “Concrete Mathematics” has proved to be as suitable as any other. The original textbook for Stanford’s course on concrete mathematics was the “Mathematical Preliminaries” section in The Art of Computer Programming [173]. But the presentation in those 110 pages is quite terse, so another author (OP) was inspired to draft a lengthy set of supplementary notes. The “The heart of mathematics consists of concrete examples and concrete problems. ” -P. R. Halmos 11411 “lt is downright sinful to teach the abstract before the concrete. ” -Z. A. Melzak 12141 Concrete Ma thematics is a bridge to abstract mathematics. “The advanced reader who skips parts that appear too elementary may miss more than the less advanced reader who skips parts that appear too complex. ” -G. Pdlya [238] (We’re not bold enough to try Distinuous Mathema tics.)
PREFACE vii present book is an outgrowth of those notes;it is an expansion of,and a more leisurely introduction to,the material of Mathematical Preliminaries.Some of the more advanced parts have been omitted;on the other hand,several topics not found there have been included here so that the story will be complete. The authors have enjoyed putting this book together because the subject a concrete began to jell and to take on a life of its own before our eyes;this book almost life preserver seemed to write itself.Moreover,the somewhat unconventional approaches thrown to students sinking in a sea of we have adopted in several places have seemed to fit together so well,after abstraction” these years of experience,that we can't help feeling that this book is a kind 一W.Gottschalk of manifesto about our favorite way to do mathematics.So we think the book has turned out to be a tale of mathematical beauty and surprise,and we hope that our readers will share at least e of the pleasure we had while writing it. Since this book was born in a university setting,we have tried to capture the spirit of a contemporary classroom by adopting an informal style.Some people think that mathematics is a serious business that must always be cold and dry;but we think mathematics is fun,and we aren't ashamed to admit the fact.Why should a strict boundary line be drawn between work and play?Concrete mathematics is full of appealing patterns,the manipulations are not always easy,but the answers can be astonishingly attractive.The joys and sorrows of mathematical work are reflected explicitly in this book because they are part of our lives. Students always know better than their teachers,so we have asked the Math graffiti: first students of this material to contribute their frank opinions,as "graffiti" Kilroy wasn't Haar. in the margins.Some of these marginal markings are merely corny,some Free the group. are profound;some of them warn about ambiguities or obscurities,others Nuke the kernel. Power to the n. are typical comments made by wise guys in the back row,some are positive, N曰→P=NP. some are negative,some are zero.But they all are real indications of feelings that should make the text material easier to assimilate.(The inspiration for such marginal notes comes from a student handbook entitled Approaching Stanford,where the official university line is counterbalanced by the remarks I have only a of outgoing students.For example,Stanford says,"There are a few things marginal interest you cannot miss in this amorphous shape which is Stanford";the margin in this subject. says,"Amorphous...what the h***does that mean?Typical of the pseudo- intellectualism around here."Stanford:"There is no end to the potential of a group of students living together."Graffito:"Stanford dorms are like zoos without a keeper.“) This was the most The margins also include direct quotations from famous mathematicians enjoyable course of past generations,giving the actual words in which they announced some I've ever had.But it might be nice of their fundamental discoveries.Somehow it seems appropriate to mix the to summarize the words of Leibniz,Euler,Gauss,and others with those of the people who material as you will be continuing the work.Mathematics is an ongoing endeavor for people go along. everywhere;many strands are being woven into one rich fabric
‘I a concrete life preserver thrown to students sinking in a sea of abstraction.” - W. Gottschalk Math graffiti: Kilroy wasn’t Haar. Free the group. Nuke the kernel. Power to the n. N=l j P=NP. I have only a marginal interest in this subject. This was the most enjoyable course I’ve ever had. But it might be nice to summarize the material as you go along. PREFACE vii present book is an outgrowth of those notes; it is an expansion of, and a more leisurely introduction to, the material of Mathematical Preliminaries. Some of the more advanced parts have been omitted; on the other hand, several topics not found there have been included here so that the story will be complete. The authors have enjoyed putting this book together because the subject began to jell and to take on a life of its own before our eyes; this book almost seemed to write itself. Moreover, the somewhat unconventional approaches we have adopted in several places have seemed to fit together so well, after these years of experience, that we can’t help feeling that this book is a kind of manifesto about our favorite way to do mathematics. So we think the book has turned out to be a tale of mathematical beauty and surprise, and we hope that our readers will share at least E of the pleasure we had while writing it. Since this book was born in a university setting, we have tried to capture the spirit of a contemporary classroom by adopting an informal style. Some people think that mathematics is a serious business that must always be cold and dry; but we think mathematics is fun, and we aren’t ashamed to admit the fact. Why should a strict boundary line be drawn between work and play? Concrete mathematics is full of appealing patterns; the manipulations are not always easy, but the answers can be astonishingly attractive. The joys and sorrows of mathematical work are reflected explicitly in this book because they are part of our lives. Students always know better than their teachers, so we have asked the first students of this material to contribute their frank opinions, as “grafhti” in the margins. Some of these marginal markings are merely corny, some are profound; some of them warn about ambiguities or obscurities, others are typical comments made by wise guys in the back row; some are positive, some are negative, some are zero. But they all are real indications of feelings that should make the text material easier to assimilate. (The inspiration for such marginal notes comes from a student handbook entitled Approaching Stanford, where the official university line is counterbalanced by the remarks of outgoing students. For example, Stanford says, “There are a few things you cannot miss in this amorphous shape which is Stanford”; the margin says, “Amorphous . . . what the h*** does that mean? Typical of the pseudointellectualism around here.” Stanford: “There is no end to the potential of a group of students living together.” Grafhto: “Stanford dorms are like zoos without a keeper.“) The margins also include direct quotations from famous mathematicians of past generations, giving the actual words in which they announced some of their fundamental discoveries. Somehow it seems appropriate to mix the words of Leibniz, Euler, Gauss, and others with those of the people who will be continuing the work. Mathematics is an ongoing endeavor for people everywhere; many strands are being woven into one rich fabric
viii PREFACE This book contains more than 500 exercises,divided into six categories: I see: Concrete mathemat- ● Warmups are exercises that EvERx READER should try to do when first ics means drilling reading the material. Basics are exercises to develop facts that are best learned by trying one's own derivation rather than by reading somebody else's, The homework was tough but I leamed Homework exercises are problems intended to deepen an understand- a lot.It was worth ing of material in the current chapter every hour. Exam problems typically involve ideas from two or more chapters si- multaneously;they are generally intended for use in take-home exams Take-home exams (not for in-class exams under time pressure). are vital-keep them. ● Bonus problems go beyond what an average student of concrete math- ematics is expected to handle while taking a course based on this book; Exams were harder they extend the text in interesting ways. than the homework led me to expect. Research problems may or may not be humanly solvable,but the ones presented here seem to be worth a try (without time pressure). Answers to all the exercises appear in Appendix A,often with additional infor- mation about related results.(Of course,the "answers"to research problems are incomplete;but even in these cases,partial results or hints are given that might prove to be helpful.)Readers are encouraged to look at the answers, especially the answers to the warmup problems,but only making a serious attempt to solve the problem without peeking. Cheaters may pass We have tried in Appendix C to give proper credit to the sources of this course by just copying the an- each exercise,since a great deal of creativity and/or luck often goes into swers,but they're the design of an instructive problem.Mathematicians have unfortunately only cheating developed a tradition of borrowing exercises without any acknowledgment: themselves. we believe that the opposite tradition,practiced for example by books and magazines about chess (where names,dates,and locations of original chess problems are routinely specified)is far superior.However,we have not been Difficult exams able to pin down the sources of many problems that have become part of the don't take into ac- folklore.If any reader knows the origin of an exercise for which our citation count students who have other classes is missing or inaccurate,we would be glad to learn the details so that we can to prepare for. correct the omission in subsequent editions of this book. The typeface used for mathematics throughout this book is a new design by Hermann Zapf[310],commissioned by the American Mathematical Society and developed with the help of a committee that included B.Beeton,R.P Boas,L.K.Durst,D.E Knuth,P.Murdock,R.S.Palais,P.Renz,E.Swanson, S.B.Whidden,and W.B.Woolf.The underlying philosophy of Zapfs design is to capture the flavor of mathematics as it might be written by a mathemati- cian with excellent handwriting.A handwritten rather than mechanical style is appropriate because people generally create mathematics with pen,pencil
viii PREFACE This book contains more than 500 exercises, divided into six categories: I see: Warmups are exercises that EVERY READER should try to do when first Concrete mathematits meanS dri,,inp reading the material. Basics are exercises to develop facts that are best learned by trying one’s own derivation rather than by reading somebody else’s, Homework exercises are problems intended to deepen an understanding of material in the current chapter. Exam problems typically involve ideas from two or more chapters simultaneously; they are generally intended for use in take-home exams (not for in-class exams under time pressure). Bonus problems go beyond what an average student of concrete mathematics is expected to handle while taking a course based on this book; they extend the text in interesting ways. The homework was tough but I learned a lot. It was worth every hour. Take-home exams are vital-keep them. Exams were harder than the homework led me to exoect. Research problems may or may not be humanly solvable, but the ones presented here seem to be worth a try (without time pressure). Answers to all the exercises appear in Appendix A, often with additional information about related results. (Of course, the “answers” to research problems are incomplete; but even in these cases, partial results or hints are given that might prove to be helpful.) Readers are encouraged to look at the answers, especially the answers to the warmup problems, but only AFTER making a serious attempt to solve the problem without peeking. We have tried in Appendix C to give proper credit to the sources of each exercise, since a great deal of creativity and/or luck often goes into the design of an instructive problem. Mathematicians have unfortunately developed a tradition of borrowing exercises without any acknowledgment; we believe that the opposite tradition, practiced for example by books and magazines about chess (where names, dates, and locations of original chess problems are routinely specified) is far superior. However, we have not been able to pin down the sources of many problems that have become part of the folklore. If any reader knows the origin of an exercise for which our citation is missing or inaccurate, we would be glad to learn the details so that we can correct the omission in subsequent editions of this book. The typeface used for mathematics throughout this book is a new design by Hermann Zapf [310], commissioned by the American Mathematical Society and developed with the help of a committee that included B. Beeton, R. P. Boas, L. K. Durst, D. E. Knuth, P. Murdock, R. S. Palais, P. Renz, E. Swanson, S. B. Whidden, and W. B. Woolf. The underlying philosophy of Zapf’s design is to capture the flavor of mathematics as it might be written by a mathematician with excellent handwriting. A handwritten rather than mechanical style is appropriate because people generally create mathematics with pen, pencil, Cheaters may pass this course by just copying the answers, but they’re only cheating themselves. Difficult exams don’t take into account students who have other classes to prepare for
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
