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.Thevi 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. Mean￾while, 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 prob￾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￾mentary number theory, binomial coefficients, generating functions, discrete probability, and asymptotic methods. The emphasis is on manipulative tech￾nique 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 in￾finite integration). 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. The original textbook for Stanford’s course on concrete mathematics was the “Mathematical Preliminaries” section in The Art of Computer Program￾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 “The heart of math￾ematics consists of concrete exam￾ples and concrete problems. ” -P. R. Halmos 11411 “lt is downright sinful to teach the abstract before the concrete. ” -Z. A. Melzak 12141 Concrete Ma the￾matics is a bridge to abstract mathe￾matics. “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 Math￾ema tics.)