Holi

CONCRETE
MATHEMATICS

Dedicated to Leonhard Euler (1707-l 783)

CONCRETE MATHEMATICS

Dedicated to Leonhard Euler (1707-l 783)

CONCRETE MATHEMATICS
AT&T Bell Laboratories

Ronald L. Graham Donald E. Knuth
Stanford University

Oren Patashnik
Stanford University

A
ADDISON-WESLEY PUBLISHING COMPANY New York Reading, Massachusetts Menlo Park, California Don Mills, OntarioAmsterdam Bonn Wokingham, England Sydney Singapore Tokyo Madrid San Juan

Library of Congress Cataloging-in-Publication Data
Graham, Ronald Lewis, 1935Concrete mathematics : a foundation for computer science / Ronald L. Graham, Donald E. Knuth, Oren Patashnik. xiii,625 p. 24 cm. Bibliography: p. 578 Includes index. ISBN o-201-14236-8 1. Mathematics--19612. Electronic data processing--Mathematics.I. Knuth, Donald Ervin, 1938. II. Patashnik, Oren, 1954.

III. Title. QA39.2.C733 1988 510--dc19

88-3779 CIP

Sixth

printing,

with

corrections,

October

1990

Copyright @ 1989 by Addison-Wesley Publishing Company 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, mechanical,photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. Published simultaneously
in Canada.

FGHIJK-HA-943210

Preface
annually at Stanford University since 1970. About fifty students have taken it each year-juniors and seniors, but mostly graduate students-and alumni such matters is of these classes have begunto spawn similar courses elsewhere. Thus the time what prefaces are supposed to be seems ripe to present the material to a wider audience (including sophomores). about.” It was a dark and stormy decade when Concrete Mathematics was born. - P. R. Halmos 11421 Long-held values were constantly being questioned during those turbulent years; college campuses were hotbeds of controversy. The collegecurriculum 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] “People do acquire even asked, “Can mathematics be saved?” One of the present authors hada little brief author- embarked on a series of books called The Art of Computer Programming, and ity by equipping in writing the first volume he (DEK) had found that there were mathematical themselves with tools missing from his repertoire; the mathematics he needed for a thorough, jargon: they can pontificate and air a well-grounded understanding of computer programs was quite different fromsuperficial expertise. what he’d learned as a mathematics major in college. So he introduced a new But what we should course, teaching what he wished somebody had taught him. ask of educated 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 rapspeechify about, idly beingswept out of the modern mathematical curriculum by a new wave nor even what they of abstract ideas popularly called the “New Math!’ Abstract mathematics is a know about the existing corpus wonderful subject, and there’s nothing wrong with it: It’s beautiful, general, of mathematical and useful. But its adherents had become deluded that the rest of mathematknowledge, but ics was inferior and nolonger worthy of attention. The goal of generalization rather what can they now do with had become so fashionable that a generation of mathematicians had become their learning and unable to relish beauty in the particular, to enjoy the challenge of solving whether they can actually solve math- quantitative problems, or to appreciate the value of technique. Abstract mathematical problems ematics was...