Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
As happens from time to time, I posted this the same time that Robert Israel posted his comment - and so he deserves equal pride in the answer. –  mixedmath Apr 29 '11 at 5:58
    
Equal thanks to you! –  Arthur Skirvin Apr 29 '11 at 6:29

Can someone show me where (n+2)Cn+1 = (4n+2)Cn comes from ? Thanks.

share|improve this answer
2  
Welcome to MSE! This is the answer area. This is really new question and should be posted as such. Regards –  Amzoti Mar 21 '13 at 15:48
1  
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. –  Sam DeHority Mar 21 '13 at 16:00
1  
If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. –  MITjanitor Mar 21 '13 at 16:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.