CONCRETE
MAT H E MAT I C S
Second Edition
Ronald L. Graham
AT&T Bell Laboratories
Donald E. Knuth
Stanford University
Oren Patashnik
Center for Communications Research
, Preface
\Audience, level, THIS BOOK IS BASED on a course of the same name that has been taught
and treatment | annually at Stanford University since 1970. About fty students have taken it
a description of
such matters is each year | juniors and seniors, but mostly graduate students | and alumni
what prefaces are of these classes have begun to spawn similar courses elsewhere. Thus the time
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 [173]
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]
\People do acquire a even asked, \Can mathematics be saved?" One of the present authors had
little brief author- embarked on a series of books called The Art of Computer Programming, and
ity by equipping
themselves with in writing the rst volume he (DEK) had found that there were mathematical
jargon: they can tools missing from his repertoire; the mathematics he needed for a thorough,
ponti cate and air a well-grounded understanding of computer programs was quite di erent from
super cial expertise.
what he'd learned as a mathematics major in college. So he introduced a new
But what we should
ask of educated course, teaching what he wished somebody had taught him.
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 rap-
speechify about,
nor even what they idly being swept out of the modern mathematical curriculum by a new wave
know about the of abstract ideas popularly called the \New Math." Abstract mathematics is a
existing corpus wonderful subject, and there's nothing wrong with it: It's beautiful, general,
of mathematical
knowledge, but
and useful. But its adherents had become deluded that the rest of mathemat-
rather what can ics was inferior and no longer worthy of attention. The goal of generalization
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 math-
ematical problems ematics was becoming inbred and losing touch with reality; mathematical ed-
arising in practice. ucation needed a concrete counterweight in order to restore a healthy balance.
In short, we look for
deeds not words." When DEK taught Concrete Mathematics at Stanford for the rst time,
|J. Hammersley [176] he explained the somewhat strange title by saying that it was his attempt
v
,
, 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 compacti cation. (Several students from the civil engineering \The heart of math-
department got up and quietly left the room.) ematics consists
of concrete exam-
Although Concrete Mathematics began as a reaction against other trends, 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 [172]
\solidi ed" and proved to be valuable in a variety of new applications. Mean-
while, independent con rmation 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 [267]. sinful to teach the
abstract before the
The material of concrete mathematics may seem at rst to be a disparate concrete."
bag of tricks, but practice makes it into a disciplined set of tools. Indeed, the |Z. A. Melzak [267]
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-
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 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
mentary number theory, binomial coe cients, generating functions, discrete reader who skips
parts that appear
probability, and asymptotic methods. The emphasis is on manipulative tech- too elementary may
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
reader who skips
greatest-integer function and nite summation) as a student of calculus is parts that appear
familiar with continuous operations (like the absolute-value function and in- too complex."
nite integration). |G. Polya [297]
Notice that this list of topics is quite di erent 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- ematics.)
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
MAT H E MAT I C S
Second Edition
Ronald L. Graham
AT&T Bell Laboratories
Donald E. Knuth
Stanford University
Oren Patashnik
Center for Communications Research
, Preface
\Audience, level, THIS BOOK IS BASED on a course of the same name that has been taught
and treatment | annually at Stanford University since 1970. About fty students have taken it
a description of
such matters is each year | juniors and seniors, but mostly graduate students | and alumni
what prefaces are of these classes have begun to spawn similar courses elsewhere. Thus the time
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 [173]
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]
\People do acquire a even asked, \Can mathematics be saved?" One of the present authors had
little brief author- embarked on a series of books called The Art of Computer Programming, and
ity by equipping
themselves with in writing the rst volume he (DEK) had found that there were mathematical
jargon: they can tools missing from his repertoire; the mathematics he needed for a thorough,
ponti cate and air a well-grounded understanding of computer programs was quite di erent from
super cial expertise.
what he'd learned as a mathematics major in college. So he introduced a new
But what we should
ask of educated course, teaching what he wished somebody had taught him.
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 rap-
speechify about,
nor even what they idly being swept out of the modern mathematical curriculum by a new wave
know about the of abstract ideas popularly called the \New Math." Abstract mathematics is a
existing corpus wonderful subject, and there's nothing wrong with it: It's beautiful, general,
of mathematical
knowledge, but
and useful. But its adherents had become deluded that the rest of mathemat-
rather what can ics was inferior and no longer worthy of attention. The goal of generalization
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 math-
ematical problems ematics was becoming inbred and losing touch with reality; mathematical ed-
arising in practice. ucation needed a concrete counterweight in order to restore a healthy balance.
In short, we look for
deeds not words." When DEK taught Concrete Mathematics at Stanford for the rst time,
|J. Hammersley [176] he explained the somewhat strange title by saying that it was his attempt
v
,
, 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 compacti cation. (Several students from the civil engineering \The heart of math-
department got up and quietly left the room.) ematics consists
of concrete exam-
Although Concrete Mathematics began as a reaction against other trends, 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 [172]
\solidi ed" and proved to be valuable in a variety of new applications. Mean-
while, independent con rmation 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 [267]. sinful to teach the
abstract before the
The material of concrete mathematics may seem at rst to be a disparate concrete."
bag of tricks, but practice makes it into a disciplined set of tools. Indeed, the |Z. A. Melzak [267]
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-
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 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
mentary number theory, binomial coe cients, generating functions, discrete reader who skips
parts that appear
probability, and asymptotic methods. The emphasis is on manipulative tech- too elementary may
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
reader who skips
greatest-integer function and nite summation) as a student of calculus is parts that appear
familiar with continuous operations (like the absolute-value function and in- too complex."
nite integration). |G. Polya [297]
Notice that this list of topics is quite di erent 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- ematics.)
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
