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!
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}$ ?