View Single Post
  #5  
Old 09-20-2005, 06:02 PM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default Re: Recurrence Relation to Closed Form

Given F(N) = F(N-1)*(2N-1)*(2N)/2 and F(0)=1 what is F?

First you might notice this recurrence relation has the form
F(N) = F(N-1) * G(N).

Any recurrence relation of this form has a "telescoping product" solution:

F(N) = F(0)* Product[ G(i), {i, 1, N}].

So,

F(N) = 1 * Product[ (2 i)*(2 i -1)/2, {i, 1, N}]

= (2N)!! (2N-1)!! / 2^N
= (2N)!/2^N.

(Here x!! = x*(x-2)*(x-4)*...).
Reply With Quote