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 mathemat￾its 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 understand￾ing of material in the current chapter. Exam problems typically involve ideas from two or more chapters si￾multaneously; 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 math￾ematics 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 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 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 mathemati￾cian 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 an￾swers, but they’re only cheating themselves. Difficult exams don’t take into ac￾count students who have other classes to prepare for