Welcome to MathOverflow

Question

0

C(0) = 1
C(1) = 1
C(n+1) = Sigma(r, 0, n, C(r) x C(n-r))

Where Sigma() means: Sigma(index var, lower bound, upper bound (inclusive), function(r)) I'm not familiar with standard Latex notation as I'm not a mathematician, so please ignore the sloppy presentation of the problem.

flag	asked Nov 6 2009 at 12:40 Divye 3●1

Ho Chung Siu · Accepted Answer · 2009-11-06 12:48:44Z UTC

4

You want Catalan number

answered Nov 6 2009 at 12:48

Ho Chung Siu
1,730●1●11●20

	How can the terms of such series be obtained in general given only the recursive representation? The product within the sigma causes difficulties in evaluation of the problem. – Divye Nov 6 2009 at 12:57
	I am not familiar with combinatorics at all, so perhaps others can give you a better answer. In my understanding, one common technique of finding the general term uses the generating function (the first proof in wiki). The product in this situation looks exactly like the coefficients of multiplication of two power series. This suggests that generating function could work. – Ho Chung Siu Nov 6 2009 at 13:13

Qiaochu Yuan · Answer 2 · 2009-11-06 14:36:37Z UTC

In response to the comment to the other answer: the general technique is to write the recursion as a generating function identity. In this particular case, the identity is C(x) = 1 + x C(x)^2 and one can use the quadratic formula, then the generalized binomial theorem. More generally there are now powerful computer packages that can solve certain general classes of recursions and spit back hypergeometric series; the canonical reference here is Petovsek, Wilf, and Zeilberger. If you don't know much about generating functions, you might want to check out Wilf's "generatingfunctionology" first.

What is the simplest non-recursive formulation for the following recursive function?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.