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 pseudo￾intellectualism 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