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