What books do you recommend before 'Concrete Mathematics'?

What book(s) do you recommend before Concrete Mathematics?

Is something like "Introduction to discrete Mathematics" enough?

Solution 1:

It would help to know what math classes you've covered thus far. Knowing some basics in calculus will certainly help. From one of your comments below your question, it seems as though you haven't had any calculus, it would be good to cover some of the material typically covered in a calculus survey course, or 1st semester calculus. Spivak's Calculus was one of the recommended texts; you could also learn calculus, or supplement your study of a text, with on-line video-lectures and tutoring: I highly recommend that you visit The Khan Academy website: everything offered on the site is free, and it has built a great deal of credibility (e.g. Bill Gates has offered to sponsor the site.) Not only does the site offer lessons and exercises in calculus; it also covers geometry, trigonometry, and algebra. It is very extensive and a good resource for "brushing up" on previous learning too.

Now, from my take of the preface to Concrete Mathematics (see link to the book's preface below), the book was, by design, written to make the content accessible to a "wider audience (including [college] sophomores)", and hence, doesn't seem to assume any intensive background in college math. So, I think you could probably "jump right into" the book; if you do encounter any difficulties along the way, the book has an extensive bibliography to which you can refer, or a quick web search (Google, Wikipedia, MathWorld, etc.) of the topic causing you problems will turn up lots of resources to help you out.

However, if you are really unsure of your capacity to master Concrete Mathematics at this point in time, then by all means, prepare using some of the suggestions cited here. Discrete math might provide some preparation prior to reading Concrete Mathematics, but it seems to me that the relevant content from discrete mathematics is covered in the text. It certainly wouldn't hurt to study discrete mathematics (perhaps take a look at Kenneth Rosen's Discrete Mathematics and its Applications); it all depends on the time-frame you have available, your level of commitment, your capacity to stay focused, and the confidence you have in your abilities.

For those who aren't familiar with the book Concrete Mathematics, an overview of the text can be found here. To save you some "web surfing time", I'll quote from that webpage below:

Subject Area: CS Basics (Logics, Discrete Mathematics) in CIDEC Library.

CONCRETE MATHEMATICS: A Foundation for Computer Science, 2nd ed
Authors:
* Ronald L. GRAHAM, 1935- , AT & T Bell Laboratories
* Donald Ervin KNUTH, 1938- , Stanford University
* Oren PATASHNIK, 1954- , Center for Communications Research
Publisher : Addison-Wesley Publishing Co. - Reading, Mass.
Bibliographic : Hardcover, ISBN: 0-201-55802-5 © 1994

"...Concrete Mathematics is a blending of CONtinuous and disCRETE mathematics. "More concretely," the authors explain, "it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems." The subject matter is primarily an expansion of the Mathematical Preliminaries section in Knuth's classic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories. Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study..."

CONTENTS

PREFACE (See Preface here)

Chapter 1 Recurrent Problems 1.1 The Tower of Hanoi 1.2 Lines in the Plane 1.3 The Josephus Problem Exercises

Chapter 2 Sums 2.1 Notation 2.2 Sums and Recurrences 2.3 Manipulation of Sums 2.4 Multiple Sums 2.5 General Methods 2.6 Finite and Infinite Calculus 2.7 Infinite Sums Exercises

Chapter 3 Integer Functions 3.1 Floors and Ceilings 3.2 Floor/Ceiling Applications 3.3 Floor/Ceiling Recurrences 3.4 'mod': The Binary Operation 3.5 Floor/Ceiling Sums Exercises

Chapter 4 Number Theory 4.1 Divisibility 4.4 Factorial Factors 4.5 Relative Primality 4.6 'mod': The Congruence Relation 4.7 Independent Residues 4.8 Additional Applications 4.9 Phi and Mu Exercises

Chapter 5 Binomial Coefficients 5.1 Basic Identities 5.2 Basic Practice 5.3 Tricks of the Trade 5.4 Generating Functions 5.5 Hypergeometric Functions 5.6 Hypergeometric Transformations 5.7 Partial Hypergeometric Sums 5.8 Mechanical Summation Exercises

Chapter 6 Special Numbers 6.1 Stirling Numbers 6.2 Eulerian Numbers 6.3 Harmonic Numbers 6.4 Harmonic Summation 6.5 Bernoulli Numbers 6.6 Fibonacci Numbers 6.7 Continuants Exercises

Chapter 7 Generating Functions 7.1 Domino Theory and Change 7.2 Basic Maneuvers 7.3 Solving Recurrences 7.4 Special Generating Functions 7.5 Convolutions 7.6 Exponential Generating Functions 7.7 Dirichlet Generating Functions Exercises

Chapter 8 Discrete Probability 8.1 Definitions 8.2 Mean and Variance 8.3 Probability Generating Functions 8.4 Flipping Coins 8.5 Hashing Exercises

Chapter 9 Asymptotics 9.1 A Hierarchy 9.2 O Notation 9.3 O Manipulation 9.4 Two Asymptotic Tricks 9.5 Euler's Summation Formula 9.6 Final Summations Exercises

Solution 2:

My own feeling on this is that if you are an undergraduate in an engineering discipline, with the usual math sequence behind you (e.g. calculus I,II,III, & linear algebra), you will have a difficult time with Concrete Mathematics.

You would be much better served starting with an introductory text (I think Epp's Discrete Mathematics with Applications is excellent), and afterwards going to that book.

Concrete Mathematics is an amazing book, but it assumes you already know the basics that would be taught in a 1-semester course on the subject. The problems are superbly gauged, and even the answers (which are provided for all the exercises) often require significant thought to understand. I am currently halfway through it and am just amazed at its density, how well written it is, and how perfectly the answers help one to solve the respective exercise without just giving the result away.

But I have already been exposed to the discrete math basics and still find Concrete Mathematics is hard work.

The preface may imply it can be read by a wide audience - there may be college sophomores in engineering programs who can handle this material. But they would be the rare exception.

Solution 3:

It's never late to add an answer. Especially if it serves as reference to others. I'm a double major (senior) in CS and math. Compared to a common CS student my math knowledge is far superior, especially after taking courses in abstract algebra, real analysis, and so on that really changed my way of thinking, even more when it comes to write proofs. However, even with all these I must say that Concrete Mathematics is a tough reading. Sometimes I find myself looking at some answers in the back, because honestly it's hard material. Even though the authors, especially Knuth, are acclaimed experts, that does not mean they make the best teachers. People sometimes lie when they say it was not that hard just to seem smart. Do not believe them. The authors assume too much from the readers to be honest. You will struggle, but you will learn. If you don't know about a concept search the definition somewhere else, compare it to the one in the book if there's any. You will forget many things momentarily but in the long run they'll be there, and when the moment comes you will remember you saw it in a book, you will review it and you will apply it. That's all you need.

Solution 4:

Sorry for being late to the party, but I have some recommendations that I feel are very helpful for prepping for Concrete Mathematics. I agree with all previously posted answers and think they are pretty on key. I haven't read Concrete Mathematics yet, but I am currently taking a discrete math course at Utah State. After taking Calc. I, and II and my current Discrete Math course I feel comfortable with all the notation I have seen so far in the book. Linear Algebra was not a pre-requisite for Discrete Math at my university, but at times I wish I had taken it. If this book is a reflection of my current class (which in seems in the most part to be) I would say you can most likely get by without Linear Algebra (by only learning as you are going), but I am considering taking a course in it online now since I wish I better understood the concepts.

Now onto my recommendations. I know you asked for books, but I personally feel you should try and take some math courses from MIT OpenCourseWare. Yeah it isn't books, but you can download and watch course lectures from the professors, and they have assigned books for the courses that you can buy yourself. They also have assigned homework that you can work through and other course materials.

As suggested by others I would take these courses.

• Single Variable Calculus (Which I believe is Calc. I and II)
• Multi Variable Calculus (Which I believe is Calc. III)
• Linear Algebra
• Mathematics for Computer Scientists (Which is Discrete Math)

I believe as well as amWhy that Khan Academy is a great resource for learning mathematics, but I really enjoy having the class room feel of taking an MIT OpenCourseWare course and personally prefer the MIT OCW over Khan Academy. I personally haven't finished the Mathematics for Computer Scientists course at MIT OCW, but I did start it to prep for my Discrete Math course at my university and it was a major help. I plan to finish Mathematics for Computer Scientists along with Concrete Mathematics, because I enjoyed taking the beggining of the OCW course so much.