The Art and Craft of Problem Solving

Thus, in particular, if we define

In:= �(a

n

• W),

6.4 RECURRENCE 217

then In + I = In + In -I. Since this also satisfies the boundary values, it must generate

the entire Fibonacci sequence. _

While it is nice to have a "simple" formula that generates the Fibonacci sequence,
knowing the recurrence formula is almost as good, and sometimes it is impossible or
extremely difficult to get a "closed-form" solution to a recurrence. A few problems at
the end of this section discuss some methods for solving recurrences,^6 but for now, let
us just concentrate on discovering some interesting recurrence formulas.

The Catalan Recurrence

In the example below, we will discover a complicated recurrence formula that turns up
in surprisingly many situations.

Example 6.4.2 The idea of a triangulation of a polygon was introduced in Exam­
ple 2.3.9 on page 48. Compute the number of different triangulations of a convex
n-gon.

Partial Solution: Experimentation yields t 3 = l,t 4 = 2,t 5 = 5. For example, here

are the five different triangulations for a convex pentagon:

Let's move on to 6-gons, trying to discover a connection between them and smaller
polygons. Fix a base, and consider the four possible vertices that we can draw a
triangle from:

Notice that these four pictures partition the triangulations. The first picture yields t 5
new triangulations (corresponding to all the ways that the pentagon above the dotted
line can be triangulated), while the second yields t 4 triangulations (the only choice
involved is triangulating the quadrilateral). Continuing this reasoning, we deduce that

t (^6) = t 5 +t 4 +t 4 +t (^5) = 14,
(^6) Also see Section 4. 3 for another general method for solving and analyzing recurrences.