Registered users can read the full content for free
Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.
Page
1
(This page has no text content)
Page
2
C O N C R E T E M A T H E M A T I C S Second Edition Dedicated to Leonhard Euler (1707{1783)
Page
3
A Foundation for Computer Science
Page
4
C O N C R E T E M A T H E M A T I C S Second Edition Ronald L. Graham AT&T Bell Laboratories Donald E. Knuth Stanford University Oren Patashnik Center for Communications Research 677 ADDISON-WESLEY PUBLISHING COMPANY Reading, Massachusetts Menlo Park, California New York Don Mills, Ontario Wokingham, England Amsterdam Bonn Sydney Singapore Tokyo Madrid San Juan Milan Paris
Page
5
Library of Congress Cataloging-in-Publication Data Graham, Ronald Lewis, 1935- Concrete mathematics : a foundation for computer science / Ronald L. Graham, Donald E. Knuth, Oren Patashnik. -- 2nd ed. xiii,657 p. 24 cm. Bibliography: p. 604 Includes index. ISBN 0-201-55802-5 1. Mathematics. 2. Computer science--Mathematics. I. Knuth, Donald Ervin, 1938- . II. Patashnik, Oren, 1954- . III. Title. QA39.2.G733 1994 510--dc20 93-40325 CIP Reproduced by Addison-Wesley from camera-ready copy supplied by the authors. Copyright c© 1994, 1989 by Addison-Wesley Publishing Company, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechan- ical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. 1 2 3 4 5 6 7 8 9 10{MA{9897969594
Page
6
Preface THIS BOOK IS BASED on a course of the same name that has been taught\Audience, level, and treatment | a description of such matters is what prefaces are supposed to be about." | P. R. Halmos [173] annually at Stanford University since 1970. About fty 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 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" [176]; other worried mathematicians [332] even asked, \Can mathematics be saved?" One of the present authors had\People do acquire a little brief author- ity by equipping themselves with jargon: they can ponticate and air a supercial 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 math- ematical problems arising in practice. In short, we look for deeds not words." | J. Hammersley [176] embarked on a series of books called The Art of Computer Programming, and in writing the rst 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 dierent 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 rap- idly 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 mathemat- ics 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 math- ematics was becoming inbred and losing touch with reality; mathematical ed- ucation needed a concrete counterweight in order to restore a healthy balance. When DEK taught Concrete Mathematics at Stanford for the rst time, he explained the somewhat strange title by saying that it was his attempt v
Page
7
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{Cech compactication. (Several students from the civil engineering \The heart of math- ematics consists of concrete exam- ples and concrete problems." | P. R. Halmos [172] 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 \solidied" and proved to be valuable in a variety of new applications. Mean- while, independent conrmation for the appropriateness of the name came from another direction, when Z. A. Melzak published two volumes entitled \It is downright sinful to teach the abstract before the concrete." | Z. A. Melzak [267] Companion to Concrete Mathematics [267]. The material of concrete mathematics may seem at rst 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) rst 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 Mathe- matics is a bridge to abstract mathe- matics. 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 uent in algebraic techniques that you will often nd 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 reader who skips parts that appear too elementary may miss more than the less advanced reader who skips parts that appear too complex." | G. Polya [297] mentary number theory, binomial coecients, 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 nite summation) as a student of calculus is familiar with continuous operations (like the absolute-value function and in- nite integration). Notice that this list of topics is quite dierent 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 enough to try Distinuous Math- ematics.) The original textbook for Stanford's course on concrete mathematics was the \Mathematical Preliminaries" section in The Art of Computer Program- ming [207]. 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
Page
8
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\. . . a concrete life preserver thrown to students sinking in a sea of abstraction." | W. Gottschalk seemed to write itself. Moreover, the somewhat unconventional approaches we have adopted in several places have seemed to t 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 ε 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 re ected explicitly in this book because they are part of our lives. Students always know better than their teachers, so we have asked the rst students of this material to contribute their frank opinions, as \grati"Math grati: Kilroy wasn't Haar. Free the group. Nuke the kernel. Power to the n . N=1 ⇒ P=NP . 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 ocial university line is counterbalanced by the remarks of outgoing students. For example, Stanford says, \There are a few thingsI have only a marginal interest in this subject. 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." Grato: \Stanford dorms are like zoos without a keeper.") The margins also include direct quotations from famous mathematiciansThis was the most enjoyable course I've ever had. But it might be nice to summarize the material as you go along. 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.
Page
9
viii PREFACE This book contains more than 500 exercises, divided into six categories: I see: Concrete mathemat- ics means drilling.• Warmups are exercises that every reader should try to do when rst 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 learned a lot. It was worth every hour. • 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 Take-home exams are vital | keep them. (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; Exams were harder than the homework led me to expect. they extend the text in interesting ways. • 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. Cheaters may pass this course by just copying the an- swers, but they're only cheating themselves. 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 specied) is far superior. However, we have not been Dicult exams don't take into ac- count students who have other classes to prepare for. 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 [227], 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 avor 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,
Page
10
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.)I'm unaccustomed to this face. The letters are upright, not italic, so that subscripts, superscripts, and ac- cents are more easily tted 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 (AaBb Cc through XxYyZz), Euler Frak- tur (AaBb Cc through XxYy Zz), and Euler Script Capitals (ABC through XYZ), as well as Euler Greek (AαBβ Γγ through XχΨψ Ωω) 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. The authors are extremely grateful to Andrei Broder, Ernst Mayr, An-Dear prof: Thanks for (1) the puns, (2) the subject matter. drew Yao, and Frances Yao, who contributed greatly to this book during the years that they taught Concrete Mathematics at Stanford. Furthermore we oer 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 rst-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,I don't see how what I've learned will ever help me. Rice, and Stanford who contributed the choice grati and helped to debug our rst drafts. Our contacts at Addison-Wesley were especially ecient 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 Oce 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.I had a lot of trou- ble in this class, but I know it sharpened my math skills and my thinking skills. This second edition features a new Section 5.8, which describes some important ideas that Doron Zeilberger discovered shortly after the rst edition went to press. Additional improvements to the rst printing can also be found on almost every page. 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 re- ward of $2.56 will gratefully be paid to the rst nder of any error, whether it is mathematical, historical, or typographical.I would advise the casual student to stay away from this course. Murray Hill, New Jersey | RLG and Stanford, California DEK May 1988 and October 1993 OP
Page
11
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. (See the general index, at the end of the book, for references to more standard notations.) Notation Name Page ln x natural logarithm: loge x 276 lg x binary logarithm: log2 x 70 log x common logarithm: log10 x 449 bxc oor: max fn | n x, integer n g 67 dxe ceiling: min fn | n x, integer n g 67 x mod y remainder: x − ybx/yc 82 fxg fractional part: x mod 1 70 ∑ f(x) δx indenite summation 48 ∑b a f(x) δx denite summation 49 xn falling factorial power: x!/(x − n)! 47, 211 xn rising factorial power: Γ(x + n)/Γ(x) 48, 211 n< subfactorial: n!/0! − n!/1! + · · ·+ (−1)nn!/n! 194 <z real part: x, if z = x + iy 64 If you don't under- stand what the x denotes at the bottom of this page, try asking your Latin professor instead of your math professor. =z imaginary part: y, if z = x + iy 64 Hn harmonic number: 1/1 + · · ·+ 1/n 29 H(x) n generalized harmonic number: 1/1x + · · ·+ 1/nx 277 x
Page
12
A NOTE ON NOTATION xi f(m)(z) mth derivative of f at z 470 [ n m ] Stirling cycle number (the \rst kind") 259 { n m } Stirling subset number (the \second kind") 258 〈 n m 〉 Eulerian number 267 n m Second-order Eulerian number 270Prestressed concrete mathematics is con- crete mathematics that's preceded by a bewildering list of notations. (am . . . a0)b radix notation for ∑m k=0 akbk 11 K(a1, . . . , an) continuant polynomial 302 F ( a, b c ∣∣∣ z ) hypergeometric function 205 #A cardinality: number of elements in the set A 39 [zn] f(z) coecient of zn in f(z) 197 [α . . β] closed interval: the set fx | α x βg 73 [m = n] 1 if m = n, otherwise 0 * 24 [mnn] 1 if m divides n, otherwise 0 * 102 [mnnn] 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, the string of letters `string' is sometimes called a \string."Also `nonstring' is a string. An expression of the form `a/bc' means the same as `a/(bc)'. Moreover, log x/log y = (log x)/(log y) and 2n! = 2(n!).
Page
13
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 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 Innite Calculus 47 2.7 Innite 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 5.3 Tricks of the Trade 186 xii
Page
14
CONTENTS xiii 5.4 Generating Functions 196 5.5 Hypergeometric Functions 204 5.6 Hypergeometric Transformations 216 5.7 Partial Hypergeometric Sums 223 5.8 Mechanical Summation 229 Exercises 242 6 Special Numbers 257 6.1 Stirling Numbers 257 6.2 Eulerian Numbers 267 6.3 Harmonic Numbers 272 6.4 Harmonic Summation 279 6.5 Bernoulli Numbers 283 6.6 Fibonacci Numbers 290 6.7 Continuants 301 Exercises 309 7 Generating Functions 320 7.1 Domino Theory and Change 320 7.2 Basic Maneuvers 331 7.3 Solving Recurrences 337 7.4 Special Generating Functions 350 7.5 Convolutions 353 7.6 Exponential Generating Functions 364 7.7 Dirichlet Generating Functions 370 Exercises 371 8 Discrete Probability 381 8.1 Denitions 381 8.2 Mean and Variance 387 8.3 Probability Generating Functions 394 8.4 Flipping Coins 401 8.5 Hashing 411 Exercises 427 9 Asymptotics 439 9.1 A Hierarchy 440 9.2 O Notation 443 9.3 O Manipulation 450 9.4 Two Asymptotic Tricks 463 9.5 Euler's Summation Formula 469 9.6 Final Summations 476 Exercises 489 A Answers to Exercises 497 B Bibliography 604 C Credits for Exercises 632 Index 637 List of Tables 657
Page
15
1 Recurrent Problems THIS CHAPTER EXPLORES three sample problems that give a feel for what's to come. They have two traits in common: They've all been investi- gated repeatedly by mathematicians; and their solutions all use the idea of recurrence, in which the solution to each problem depends on the solutions to smaller instances of the same problem. 1.1 THE TOWER OF HANOI Let's look rst at a neat little puzzle called the Tower of Hanoi, invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs:Raise your hand if you've never seen this. OK, the rest of you can cut to equation (1.1). The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller. Lucas [260] furnished his toy with a romantic legend about a much larger Tower of Brahma, which supposedly has 64 disks of pure gold resting on threeGold | wow. Are our disks made of concrete? diamond needles. At the beginning of time, he said, God placed these golden disks on the rst needle and ordained that a group of priests should transfer them to the third, according to the rules above. The priests reportedly work day and night at their task. When they nish, the Tower will crumble and the world will end. 1
Page
16
2 RECURRENT PROBLEMS It's not immediately obvious that the puzzle has a solution, but a little thought (or having seen the problem before) convinces us that it does. Now the question arises: What's the best we can do? That is, how many moves are necessary and sucient to perform the task? The best way to tackle a question like this is to generalize it a bit. The Tower of Brahma has 64 disks and the Tower of Hanoi has 8; let's consider what happens if there are n disks. One advantage of this generalization is that we can scale the problem down even more. In fact, we'll see repeatedly in this book that it's advanta- geous to look at small cases rst. It's easy to see how to transfer a tower that contains only one or two disks. And a small amount of experimentation shows how to transfer a tower of three. The next step in solving the problem is to introduce appropriate notation: name and conquer. Let's say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucas's rules. Then T1 is obviously 1, and T2 = 3. We can also get another piece of data for free, by considering the smallest case of all: Clearly T0 = 0, because no moves at all are needed to transfer a tower of n = 0 disks! Smart mathematicians are not ashamed to think small, because general patterns are easier to perceive when the extreme cases are well understood (even when they are trivial). But now let's change our perspective and try to think big; how can we transfer a large tower? Experiments with three disks show that the winning idea is to transfer the top two disks to the middle peg, then move the third, then bring the other two onto it. This gives us a clue for transferring n disks in general: We rst transfer the n − 1 smallest to a dierent peg (requiring Tn−1 moves), then move the largest (requiring one move), and nally transfer the n−1 smallest back onto the largest (requiring another Tn−1 moves). Thus we can transfer n disks (for n > 0) in at most 2Tn−1 + 1 moves: Tn 2Tn−1 + 1 , for n > 0. This formula uses ` ' instead of ` = ' because our construction proves only that 2Tn−1 + 1 moves suce; we haven't shown that 2Tn−1 + 1 moves are necessary. A clever person might be able to think of a shortcut. But is there a better way? Actually no. At some point we must move the Most of the pub- lished \solutions" to Lucas's problem, like the early one of Allardice and Fraser [7], fail to ex- plain why Tn must be 2Tn−1 + 1 . largest disk. When we do, the n − 1 smallest must be on a single peg, and it has taken at least Tn−1 moves to put them there. We might move the largest disk more than once, if we're not too alert. But after moving the largest disk for the last time, we must transfer the n−1 smallest disks (which must again be on a single peg) back onto the largest; this too requires Tn−1 moves. Hence Tn 2Tn−1 + 1 , for n > 0.
Page
17
1.1 THE TOWER OF HANOI 3 These two inequalities, together with the trivial solution for n = 0, yield T0 = 0 ; Tn = 2Tn−1 + 1 , for n > 0. (1.1) (Notice that these formulas are consistent with the known values T1 = 1 and T2 = 3. Our experience with small cases has not only helped us to discover a general formula, it has also provided a convenient way to check that we haven't made a foolish error. Such checks will be especially valuable when we get into more complicated maneuvers in later chapters.) A set of equalities like (1.1) is called a recurrence (a.k.a. recurrenceYeah, yeah . . . I seen that word before. relation or recursion relation). It gives a boundary value and an equation for the general value in terms of earlier ones. Sometimes we refer to the general equation alone as a recurrence, although technically it needs a boundary value to be complete. The recurrence allows us to compute Tn for any n we like. But nobody really likes to compute from a recurrence, when n is large; it takes too long. The recurrence only gives indirect, local information. A solution to the recurrence would make us much happier. That is, we'd like a nice, neat, \closed form" for Tn that lets us compute it quickly, even for large n. With a closed form, we can understand what Tn really is. So how do we solve a recurrence? One way is to guess the correct solution, then to prove that our guess is correct. And our best hope for guessing the solution is to look (again) at small cases. So we compute, successively, T3 = 2 ·3 + 1 = 7; T4 = 2 ·7 + 1 = 15; T5 = 2 ·15 + 1 = 31; T6 = 2 ·31 + 1 = 63. Aha! It certainly looks as if Tn = 2n − 1 , for n 0. (1.2) At least this works for n 6. Mathematical induction is a general way to prove that some statement about the integer n is true for all n n0. First we prove the statement when n has its smallest value, n0; this is called the basis. Then we prove the Mathematical in- duction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the induction). statement for n > n0, assuming that it has already been proved for all values between n0 and n − 1, inclusive; this is called the induction. Such a proof gives innitely many results with only a nite amount of work. Recurrences are ideally set up for mathematical induction. In our case, for example, (1.2) follows easily from (1.1): The basis is trivial, since T0 = 20 − 1 = 0. And the induction follows for n > 0 if we assume that (1.2) holds when n is replaced by n − 1: Tn = 2Tn−1 + 1 = 2(2n−1 − 1) + 1 = 2n − 1 . Hence (1.2) holds for n as well. Good! Our quest for Tn has ended successfully.
Page
18
4 RECURRENT PROBLEMS Of course the priests' task hasn't ended; they're still dutifully moving disks, and will be for a while, because for n = 64 there are 264−1 moves (about 18 quintillion). Even at the impossible rate of one move per microsecond, they will need more than 5000 centuries to transfer the Tower of Brahma. Lucas's original puzzle is a bit more practical. It requires 28 − 1 = 255 moves, which takes about four minutes for the quick of hand. The Tower of Hanoi recurrence is typical of many that arise in applica- tions of all kinds. In nding a closed-form expression for some quantity of interest like Tn we go through three stages: 1 Look at small cases. This gives us insight into the problem and helps us in stages 2 and 3. 2 Find and prove a mathematical expression for the quantity of interest. What is a proof? \One half of one percent pure alco- hol." For the Tower of Hanoi, this is the recurrence (1.1) that allows us, given the inclination, to compute Tn for any n. 3 Find and prove a closed form for our mathematical expression. For the Tower of Hanoi, this is the recurrence solution (1.2). The third stage is the one we will concentrate on throughout this book. In fact, we'll frequently skip stages 1 and 2 entirely, because a mathematical expression will be given to us as a starting point. But even then, we'll be getting into subproblems whose solutions will take us through all three stages. Our analysis of the Tower of Hanoi led to the correct answer, but it required an \inductive leap"; we relied on a lucky guess about the answer. One of the main objectives of this book is to explain how a person can solve recurrences without being clairvoyant. For example, we'll see that recurrence (1.1) can be simplied by adding 1 to both sides of the equations: T0 + 1 = 1 ; Tn + 1 = 2Tn−1 + 2 , for n > 0. Now if we let Un = Tn + 1, we have Interesting: We get rid of the +1 in (1.1) by adding, not by subtracting.U0 = 1 ; Un = 2Un−1 , for n > 0. (1.3) It doesn't take genius to discover that the solution to this recurrence is just Un = 2n; hence Tn = 2n − 1. Even a computer could discover this. 1.2 LINES IN THE PLANE Our second sample problem has a more geometric avor: How many slices of pizza can a person obtain by making n straight cuts with a pizza knife? Or, more academically: What is the maximum number Ln of regions
Page
19
1.2 LINES IN THE PLANE 5 dened by n lines in the plane? This problem was rst solved in 1826, by the Swiss mathematician Jacob Steiner [338].(A pizza with Swiss cheese?) Again we start by looking at small cases, remembering to begin with the smallest of all. The plane with no lines has one region; with one line it has two regions; and with two lines it has four regions: L0 = 1 1 L1 = 2 ³³³³³³1 2 L2 = 4 £ £ £ £ £ £ ³³³³³³1 2 34 (Each line extends innitely in both directions.) Sure, we think, Ln = 2n; of course! Adding a new line simply doubles the number of regions. Unfortunately this is wrong. We could achieve the doubling if the nth line would split each old region in two; certainly it can split an old region in at most two pieces, since each old region is convex. (AA region is convex if it includes all line segments be- tween any two of its points. (That's not what my dictionary says, but it's what mathematicians believe.) straight line can split a convex region into at most two new regions, which will also be convex.) But when we add the third line | the thick one in the diagram below | we soon nd that it can split at most three of the old regions, no matter how we've placed the rst two lines: £ £ £ £ £ £ hhhhhhhhhhhhhh 2 4a 4b 3b 1b 1a 3a Thus L3 = 4 + 3 = 7 is the best we can do. And after some thought we realize the appropriate generalization. The nth line (for n > 0) increases the number of regions by k if and only if it splits k of the old regions, and it splits k old regions if and only if it hits the previous lines in k− 1 dierent places. Two lines can intersect in at most one point. Therefore the new line can intersect the n−1 old lines in at most n−1 dierent points, and we must have k n. We have established the upper bound Ln Ln−1 + n , for n > 0. Furthermore it's easy to show by induction that we can achieve equality in this formula. We simply place the nth line in such a way that it's not parallel to any of the others (hence it intersects them all), and such that it doesn't go
Page
20
6 RECURRENT PROBLEMS through any of the existing intersection points (hence it intersects them all in dierent places). The recurrence is therefore L0 = 1 ; Ln = Ln−1 + n , for n > 0. (1.4) The known values of L1, L2, and L3 check perfectly here, so we'll buy this. Now we need a closed-form solution. We could play the guessing game again, but 1, 2, 4, 7, 11, 16, . . . doesn't look familiar; so let's try another tack. We can often understand a recurrence by \unfolding" or \unwinding" it all the way to the end, as follows: Ln = Ln−1 + n = Ln−2 + (n − 1) + n Unfolding? I'd call this \plugging in."= Ln−3 + (n − 2) + (n − 1) + n = L0 + 1 + 2 + · · ·+ (n − 2) + (n − 1) + n = 1 + Sn , where Sn = 1 + 2 + 3 + · · ·+ (n − 1) + n. In other words, Ln is one more than the sum Sn of the rst n positive integers. The quantity Sn pops up now and again, so it's worth making a table of small values. Then we might recognize such numbers more easily when we see them the next time: n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Sn 1 3 6 10 15 21 28 36 45 55 66 78 91 105 These values are also called the triangular numbers, because Sn is the num- ber of bowling pins in an n-row triangular array. For example, the usual four-row array qq qq q qq q q q has S4 = 10 pins. To evaluate Sn we can use a trick that Gauss reportedly came up with in 1786, when he was nine years old [88] (see also Euler [114, part 1, §415]): It seems a lot of stu is attributed to Gauss | either he was really smart or he had a great press agent. Maybe he just had a magnetic personality. Sn = 1 + 2 + 3 + · · · + (n − 1) + n + Sn = n + (n − 1) + (n − 2) + · · · + 2 + 1 2Sn = (n + 1) + (n + 1) + (n + 1) + · · · + (n + 1) + (n + 1) We merely add Sn to its reversal, so that each of the n columns on the right sums to n + 1. Simplifying, Sn = n(n + 1) 2 , for n 0. (1.5)
The above is a preview of the first 20 pages. Register to read the complete e-book.
AI Reading Assistant
Whole-book reading guide from stratified index samples; jump to passages in the text
AI guide
【One-Line Pitch】
A hands-on tour of the mathematics that underpins algorithm analysis, teaching you to solve recurrences, manipulate sums, and count things precisely. Best for programmers and students who want the problem-solving toolkit behind Knuth's *The Art of Computer Programming* rather than abstract proofs.
【Book Arc】
- **Opening (~0%–10%)**: Recurrent problems (Tower of Hanoi, lines in the plane, Josephus) establish the book's method: guess a pattern from small cases, then prove it by induction. This stage trains the reflex of turning a recurrence into a closed form.
- **Early (~10%–30%)**: Sums and integer functions. Sigma-notation, manipulating and interchanging sums, finite/infinite calculus, then floors, ceilings, and `mod` as tools for exact counting.
- **Early–Middle (~30%–48%)**: Number theory and binomial coefficients. Divisibility, primes, gcd, congruences, the Stern–Brocot tree, then Pascal's triangle, Vandermonde convolution, and "tricks of the trade" for identities.
- **Middle (~48%–65%)**: Special numbers (Stirling, Eulerian, harmonic, Bernoulli) and generating functions — the machinery for solving recurrences and extracting coefficients.
- **Late (~65%–85%)**: Discrete probability and asymptotic methods, connecting exact formulas to growth-rate estimates.
- **Ending (~85%–100%)**: The "continuum" material — a capstone applying the accumulated toolkit to harder problems. (Excerpts do not cover the final chapters in detail.)
【Key Takeaways】
- **Guess, then prove** (Opening): The Josephus problem shows the core loop — tabulate small values, spot a pattern like J(2^m + l) = 2l + 1, then verify by induction. This is the book's signature habit.
- **Recurrences are the entry point** (Opening): Hanoi and Josephus recurrences are reduced by halving n, making even J(1,000,000) cheap to compute before a closed form is found.
- **Sums are a manipulable object** (Early): Sigma-notation, changing order of summation, and perturbation methods let you reshape a hard sum into an easy one — "you can't scale peaks climbing only uphill."
- **Floors and ceilings are inflexible but tameable** (Early): Rules like ⌊x+n⌋ = ⌊x⌋+n and the inequality equivalences (3.7) let you insert or delete brackets; the generalized Josephus algorithm (3.19) is a payoff.
- **Number theory powers counting** (Early–Middle): gcd, relative primality, and congruences (including CRT-style residue reconstruction) are practical tools, not just theory.
- **Binomial identities have repeatable tricks** (Middle): Vandermonde convolution, parallel summation, and "going halves" turn ad hoc manipulations into a systematic craft.
- **Infinite sums need care** (Early): The 1+2+4+… = −1 paradox warns that finite-sum rules don't always carry over; know which class of infinite sums is safe.
【Reading Tips】
- **Work the exercises**: This is a problem book at heart; the value comes from doing, not reading. Skim theory, then attempt the starred problems.
- **Deep-read Chapters 1–2**: The guess-and-prove and sum-manipulation methods recur throughout; master them before moving on.
- **Treat later chapters as reference**: Generating functions and asymptotics are dense — return to them when a specific problem demands them.
- **Watch the margin notes**: They carry intuition and warnings (e.g., the infinite-sum paradox) that the main text compresses.
【Coverage Limits】
Excerpts concentrate on the opening through binomial coefficients (~0%–48%); later chapters on special numbers, generating functions, probability, and asymptotics are only lightly represented, so this guide's late-book arc is inferred from the table of contents.
Passage locations
Excerpt 1
nce makes it possible to build a table of small values very quickly. Perhaps we'll be able to spot a pattern and guess the answer. n 1 2 3 4 5 6 7 8 9 10 11...
View in text
Excerpt 2
ny is going on; how can we get a negative number by summing puter with innite positive quantities? It seems better to leave T undened; or perhaps we should w...
View in text
Excerpt 3
nd only if kp(mp + np) = 0, when mp and np are nonnegative. There's a beautiful way to construct the set of all nonnegative fractions m/n with m ⊥ n, called...
View in text
Excerpt 4
m this one if we set z = x/y and multiply both sides by yr. We have proved the binomial theorem only when r is a nonnegative in- teger, by using a combinator...
View in text
Recommended for You
{{#thumbnailUrl}}
{{/thumbnailUrl}}
{{^thumbnailUrl}}
{{/thumbnailUrl}}
Loading recommended books...
Failed to load, please try again later
Tip the Site
Scan the WeChat Pay or Alipay code to tip. No login required.
WeChat Pay
Alipay