You start with the recurrence C_n = Σ_i=0^n-1 C_i C_{n-i-1} for n ≥ 1, and C_0 = 1. That is, the number of binary trees of size n is 1 if n is zero, and the sum over all possible ways of building a tree of size n out of two subtrees, the first of size i, and the second of size n-i-1. You say to yourself, hm, I'll try generating functions. That means sum both sides over x^n and give the left side a name. So we get some function g(x) such that:
g(x) = Σ_n=0^∞ C_n x^n = 1 + Σ_n=0^∞ Σ_i=0^n-1 x^n C_i C_{n-i-1}
(We get the "1 +" because we know C_0 is 1) Now the body of the sum on the right-hand side very naturally suggests the regrouping
x (C_i x^i) (C_{n-i-1} x^(n-i-1))
because this lets us reindex and separate sums:
g = 1 + x Σ_n=0^∞ Σ_i=0^{n-1} (C_i x^i) (C_{n-i-1} x^(n-i-1))
= 1 + x Σ_i=0^∞ Σ_v=0^∞ (C_i x^i) (C_v x^v)
= 1 + x (Σ_i=0^∞ C_i x^i) (Σ_v=0^∞ C_v x^v)
= 1 + x g^2
If you've seen generating functions before, you know "g = 1 + x g^2" is a very standard result of thinking about the datatype
'a tree ::= empty | node of 'a * tree * tree
which makes sense in any event, since catalan numbers are supposed, after all, to count binary trees with n internal nodes.
Anyway, you dig up the quadratic equation from the high-school section of your brain, and out comes
g(x) = (1 - sqrt(1 - 4x)) / 2x
Now what? Well, the coefficients of the power series for g(x) are the Catalan numbers. How do we compute them? Standard Taylor series stuff tell us we can always get out the nth coefficient of the series by differentiating n times, evaluating at zero, and dividing by n!. But differentiating with the square root upstairs and the non-vanishing 2x downstairs is a pain in the ass. Let's just do sqrt(1 + x) instead.
(1+x)^(1/2) = (1+x)^(1/2)
(d/dx)((1+x)^(1/2)) = (1/2)(1+x)^(-1/2)
(d/dx)^2((1+x)^(1/2)) = (1/2)(-1/2)(1+x)^(-3/2)
(d/dx)^3((1+x)^(1/2)) = (1/2)(-1/2)(-3/2)(1+x)^(-5/2)
(d/dx)^4((1+x)^(1/2)) = (1/2)(-1/2)(-3/2)(-5/2)(1+x)^(-7/2)
...
evaluating at zero and dividing by n! gives us the coefficients of the power series:
(1 / 0!) x^0 +
((1/2) / 1!) x^1 +
((1/2)(-1/2) / 2!) x^2 +
((1/2)(-1/2)(-3/2) / 3!) x^3 +
((1/2)(-1/2)(-3/2)(-5/2) / 4!) x^4 + ...
So the formula for the nth coefficient here (if n ≥ 1) is
-(-1/2)^n (1 * 3 * 5 ... * 2n - 1) / n!
How can we deal with that product of odd numbers? Well,
(2n - 2)! = (1 * 3 * 5 * .... 2n - 1) * (2 * 4 * 6 * ... 2n - 2)
= (1 * 3 * 5 * .... 2n - 1) * 2^{n-1} (n-1)!
so it's equal to 2((2n-2)! / 2^n (n-1)!) Our formula for the nth coefficient can be rewritten as
-(-1/4)^n (2/n) ((2n-2)!/(n-1)!(n-1)!)
which is nice because we can mention binomial coefficients now:
-(-1/4)^n (2/n) (2n-2 choose n-1)
This means (remembering that the 0th coefficient for sqrt(1+x) is 1) that
sqrt(1+x) = 1 - 2Σ_{n=0}^∞ (-1/4)^n (1/n) (2n-2 choose n-1) x^n
Here's where the magic really happens! It's delightful how the nastiness of this formula and the nastiness of the quadratic equation solution cancel each other out nicely.
If we substitute -4y for x that (-1/4)^n goes away:
sqrt(1-4y) = 1 - 2Σ_{n=0}^∞ (1/n) (2n-2 choose n-1) y^n
And if we hit both sides with 1, the "1 - " on the right goes away:
1 - sqrt(1-4y) = 2Σ_{n=0}^∞ (1/n) (2n-2 choose n-1) y^n
Divide by 2:
(1 - sqrt(1-4y))/2 = Σ_{n=0}^∞ (1/n) (2n-2 choose n-1) y^n
and now dividing by y, in generatingfunction-land, means a mere reindexing substitution of n+1 for n inside the sum:
(1 - sqrt(1-4y))/2y = Σ_{n=0}^∞ (1/(n+1)) (2n choose n) y^n
bingo! The nth catalan number is
(2n choose n) / (n+1)
quod erat trovitum or whatever the latin is for "which was to have been found".