From: Robin Chapman Subject: Re: recurrence relationship Date: Fri, 07 Nov 1997 04:51:04 -0600 Newsgroups: sci.math In article , 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