#5
|
|||
|
|||
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)*...). |
|
|