# Show that the Catalan numbers are given by this recurrence relation

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

-
Hint: start with the definition of the Catalan numbers, written out in terms of factorials. Plug this in to the recurrence, divide the left side by the right side, and see if you can simplify the result to 1. – Robert Israel Apr 29 '11 at 5:55
Great! That worked out nicely. Sort of had a facepalm moment after reading that. Thank you! – Arthur Skirvin Apr 29 '11 at 6:27

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