From: Robin Chapman <rjc@maths.ex.ac.uk>
Subject: Re: recurrence relationship
Date: Fri, 07 Nov 1997 04:51:04 -0600
Newsgroups: sci.math

In article <pm243-0611970111150001@mac008.joh.cam.ac.uk>,
  pm243@cam.ac.uk (Pak-San Man) wrote:
>
> Are there any analytical methods of finding a general solution for:
>
> p(2) = 1
> p(3) = 1
>
> p(n) = p(2)p(n-1) + p(3)p(n-2) + p(4)p(n-3) + ... + p(n-1)p(2) ?
>
> The answer to this is:
>         1
> p(n)= ----- [(2n-4) Choose (n-2)]
>        n-1
>
> I'm shown one way using generating functions :
>
>  let q(n) = p(n+1)
>                            n
>  Then let Q(t) = sum q(n).t
>                  n>0
>
> Any other methods?

IMHO the generating function method is by far the nicest.

These are usually known as Catalan numbers and denoted by C_n = d(n+2) so
that C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5 etc. Then the recurrence becomes
C_{n+1} = C_0 C_n + C_1 C_{n-1} + C_2 C_{n-2} + ... + C_n C_0 and the
formula is C_n = (2n choose n)/(n+1) = (2n)!/(n!(n+1)!). They have many
combinatorial interpretations. Richard Stanley lists 52 of them in a
chapter from his forthcoming book Enumerative Combinatorics II available
at http://www-math.mit.edu/~rstan/ec/ec.html . Jos'e Nieto has already
posted a nice proof based on combinatorial ideas.

Here is a proof based just on the recurrence. It's takem from H. D"orrie's
book, 100 Problems in Elementary Mathematics, reprinted by Dover. He
attributes it to Urban.

To prove the formula it is sufficient, by induction, to prove that
C_{n+1}/C_n = (4n+2)/(n+2) for each n >= 1. We prove this by induction.
By reversing and adding to itself, we see that the sum C_0 C_n + 2C_1
C_{n-1} + 3C_2 C_{n-2} + ... + (n+1) C_n C_0 equals ((n+2)/2) C_{n+1}. It
suffices then to prove that this sum also equals (2n+1)C_n. But by
induction (k+1)C_k = (4k-2)C_{k-1} for 1 <= k <= n and so C_0 C_n + 2C_1
C_{n-1} + 3C_2 C_{n-2} + ... + (n+1) C_n C_0 = C_n + 2C_0 C_{n-1} + 6 C_1
C_{n-2} + ... + (4n-2) C_{n-1} C_0 = C_n + 2n C_n = (2n+1) C_n again
employing the trick of reversing the series and adding it to itself. This
completes the proof.

Robin Chapman                           "256 256 256.
Department of Mathematics                O hel, ol rite; 256; whot's
University of Exeter, EX4 4QE, UK        12 tyms 256? Bugird if I no.
rjc@maths.exeter.ac.uk                   2 dificult 2 work out."
http://www.maths.ex.ac.uk/~rjc/rjc.html  Iain M. Banks - Feersum Endjinn