Chapter 29
A Recurrence Relation for the Catalan Numbers
In dealing with the Fibonacci numbers in Part One, many of our examples were established using a second-order linear recurrence relation. However, in our dealings with the Catalan numbers so far, we have established new examples (where we believe that the Catalan numbers arise) by placing the results in each new example in a one-to-one correspondence with results from an example that was previously shown to be counted by the Catalan numbers. Now we shall introduce a recurrence relation that is satisfied by the Catalan numbers. Then in Chapters 31 and 32, we shall use this recurrence relation to introduce some further examples where this number sequence arises.
Before we get started, the reader should not expect the recurrence relation here to be as simple as the second-order linear recurrence relation we found for the Fibonacci and Lucas numbers. The relation here will be nonlinear and of a special form.
Once again, for n a nonnegative integer, we shall count the number of lattice paths from (0, 0) to (n, n). The only steps allowed are still just R: (x, y) → (x + 1, y) and U:(x, y) ↑ (x, y + 1) and the path may never rise above the line y = x, although it may touch the line at some point (k, k) where k is an integer and 0 ≤ k ≤ n. We know from Example 19.1 that the number of these lattice paths is the nth Catalan number .
This time our approach will examine those lattice paths that start at (0, 0), finish at (n, n), never ...
