5
$\begingroup$

Hey guys! I'm doing an assignment, and I'm just not sure (at all) how to start this problem. Can somebody nudge/shove me in the right directions?

Show that the Catalan numbers are given by the recurrence relation

(n+2)C$_{n+1}$ = (4n+2)C$_n$

and initial condition C$_0$ = 1

Thanks in advance!

  • 0
    Great! That worked out nicely. Sort of had a facepalm moment after reading that. Thank you!2011-04-29

1 Answers 1

4

This hint comes in two parts:

I will assume that you know that $C_n = \frac{1}{(n+1)!} \prod_{k=1}^n (4k - 2)$

Secondly, what is $\dfrac{C_{n+1}}{C_n}$ ?

  • 0
    Equal thanks to you!2011-04-29