Note that a product x1 x2x3 may be parenthesized in two

Chapter 9, Problem 44E

(choose chapter or problem)

Problem 44E

Note that a product x1 x2x3 may be parenthesized in two different ways: (x1 x2)x3 and x1(x2x3). Similarly, there are several different ways to parenthesize x1x2x3x4. Two such ways are (x1x2)(x3x4) and x1 ((x2x3)x4). Let Pn be the number of different ways to parenthesize the product x1x2 … x4. Show that if P1 = 1, then

(It turns out that the sequence P1, P2, P3, … is the same as the sequence of Catalan numbers: Pn = Cn–1 for all integers n > 1. See Example)

Example

Showing That a Sequence Given by an Explicit Formula Satisfies a Certain Recurrence Relation

The sequence of Catalan numbers, named after the Belgian mathematician Eugène Catalan (1814–1894), arises in a remarkable variety of different contexts in discrete mathematics. It can be defined as follows: For each integer n ≥ 1,

a. Find C1,C2, and C3.

b. Show that this sequence satisfies the recurrence relation  for all integers k ≥ 2

Solution

a.

b. To obtain the kth and (k – 1)st terms of the sequence, just substitute k and k – 1 in place of n in the explicit formula for C1, C2, C3,…

Then start with the right-hand side of the recurrence relation and transform it into the left-hand side: For each integer k ≥ 2,

Unfortunately, we don't have that question answered yet. But you can get it answered in just 5 hours by Logging in or Becoming a subscriber.

Becoming a subscriber
Or look for another answer

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back