Let a be the number of ways in which a convex polygon PoP Pm with n+1 sides can be partitioned into triangles by drawing n - 2 (non- intersecting) diagonals. Put a = 1.

Show that for n 2 an aan-1 + Azan-2 = + +an-191 Find the generating function and an explicit expression for an Hint: Assume that one of the diagonals passes through P, and let k be the smallest subscript such that PoP appears among the diagonals. Note: Problems 7-11 refer to section 3.

The generating functions, U, and F refer respectively to first passages through 1, returns to equilibrium, and first returns; see (3.6), (3.12), and (3.14). No calculations are necessary.