You are here

Fibonacci and Catalan Numbers: An Introduction

Ralph P. Grimaldi
John Wiley
Publication Date: 
Number of Pages: 
[Reviewed by
Alex Bogomolny
, on

The book is a comprehensive introduction to the Fibonacci and Catalan numbers and their many properties and uses. It is a tastefully written and well organized textbook that could be used for self study and easy reference. The book consists of two parts. The first seventeen chapters cover the Fibonacci and Lucas numbers, followed by 19 chapters that cover the Catalan numbers. Both parts touch on generalizations: the alternate Fibonacci, Narayana, Motzkin, Schröder, and Generalized Catalan numbers.

The two parts have a similar structure. A short historical background, the traditional motivating problems, additional examples that lead to the numbers under discussion, more theory and more examples, generalizations, a final example, bibliography. The index at the end of the book is common to the two parts as is the collection of solutions to the odd-numbered exercises. (Each chapter ends with a good many of those.)

The chapters “A Final Example?” come with a question mark. Why? After the many examples where the number families arise, the reader may tend to believe that if the first few terms of a sequence appear in a certain situation the rest will automatically follow. The two chapters serve a gentle warning that this is not always so. Inductive generalizations are no substitute for proof.

Naturally, there are plenty of proofs here that explore various techniques: mathematical induction, matrix algebra, recurrence relations, combinatorial arguments. The proofs are truly polished, with no omitted steps (that I could find), and should be followed easily by anybody with undergraduate math proficiency. The book grew out of a number of minicourses presented over a period of 20 years. As the author writes in the preface that “…the presentations were developed so that everyone in the audience would be able to understand at least some, if not a substantial amount, of the material.” And later on: “Since the book is to be regarded as an introduction, examples and, especially, proofs are presented with detailed explanations. Such examples and proofs are designed to be careful and thorough.”

I believe the author has achieved those goals. A casual reader — even after quick browse through the book — will see how ubiquitous the Fibonacci and Catalan numbers are and how broad are their applications in mathematics and natural sciences. A student who takes the study more seriously will, in addition, learn of their numerous and often beautiful and surprising properties, and master many methods of mathematical proof, even if the book is not read sequentially.

Alex Bogomolny is a semi-retired mathematician and web developer who likes to reminisce as to how, while writing his PhD thesis at the Hebrew University, he had to run his programs on a CDC-6400 at night because they required more than 120 KB of memory. He wonders at how the world changed in the past 30 years and looks forward to observing the progress of the next 30 years or so. Meanwhile, he spends time at his popular website Interactive Mathematics Miscellany and Puzzles.

Preface xi

Part One. The Fibonacci Numbers

1. Historical Background 3

2. The Problem of the Rabbits 5

3. The Recursive Definition 7

4. Properties of the Fibonacci Numbers 8

5. Some Introductory Examples 13

6. Composition and Palindromes 23

7. Tilings: Divisibility Properties of the Fibonacci Numbers 33

8. Chess Pieces on Chessboards 40

9. Optics, Botany, and the Fibonacci Numbers 46

10. Solving Linear Recurrence Relations: The Binet Form for Fn 51

11. More on α and β: Applications in Trigonometry, Physics, Continued Fractions, Probability, the Associative Law, and Computer Science 65

12. Examples from Graph Theory: An Introduction to the Lucas Numbers 79

13. The Lucas Numbers: Further Properties and Examples 100

14. Matrices, The Inverse Tangent Function, and an Infinite Sum 113

15. The ged Property for the Fibonacci Numbers 121

16. Alternate Fibonacci Numbers 126

17. One Final Example? 140

Part Two. The Catalan Numbers

18. Historical Background 147

19. A First Example: A Formula for the Catalan Numbers 150

20. Some Further Initial Examples 159

21. Dyck Paths, Peaks, and Valleys 169

22. Young Tableaux, Compositions, and Vertices and Ares 183

23. Triangulating the Interior of a Convex Polygon 192

24. Some Examples from Graph Theory 195

25. Partial Orders, Total Orders, and Topological Sorting 205

26. Sequences and a Generating Tree 211

27. Maximal Cliques, a Computer Science Example, and the Tennis Ball Problem 219

28. The Catalan Numbers at Sporting Events 226

29. A Recurrence Relation for the Catalan Numbers 231

30. Triangulating the Interior of a Convex Polygon for the Second Time 236

31. Rooted Ordered Binary Trees, Pattern Avoidance, and Data Structures 238

32. Staircases, Arrangements of Coins, Handshaking Problem, and Noncrossing Partitions 250

33. The Narayana Numbers 268

34. Related Number Sequences: The Motzkin Numbers, The Fine Numbers, and The Schröder Numbers 282

35. Generalized Catalan Numbers 290

36. One Final Example? 296

Solutions for the Odd-Numbered Exercises 301

Index 355