20.2.2. Recurrence Equation

Try these first

1. 1.

   List all valid parenthesizations for n = 1 (two numbers).

   Hint

   Think about the basic requirement for two numbers.

2. 2.

   What is C(2)?

   Hint

   Use the formula C(n) for small n values.

3. 3.

   What is the formula for C(n)?

   • C(n) = C(n-1) + C(n-2)
   • C(n) = Σ C(k) * C(n-k-1)
   • C(n) = n!

   Hint

   Think about how smaller instances contribute to the current one.

4. 4.

   True or False: The nth Catalan number represents valid parentheses strings.

   • True
   • False

   Hint

   Reflect on previous discussions about counting parenthetical arrangements.

5. 5.

   How many valid combinations exist for n = 5 using the recurrence relation?

   Hint

   Break it down using smaller known values.

6. 6.

   Prove that C(n) corresponds to valid pairs of parentheses using an example.

   Hint

   Construct examples for small n values to illustrate.