Recurrence Relation to Closed Form
Hi. Recently, I worked on a simple combinatorial problem and my initial answer was in the form of a recurrence relation. Later, I had a closed form solution. I don't think it's too hard to show that the recurrence relation and the closed form solutions are equivalent. I arrived at both independently using two different lines of thought. However, had I not happened upon the closed form solution, how could I get to it given only the recurrence relation?
Specifically...
Given F(N) = F(N-1) * Sum from i = 0 to 2(N-1)+1 of i, which is equivalent to F(N) = F(N-1)*(2N-1)*(2N)/2.
How can I ultimately get to: F(N) = (2N)! / 2^N?
I guess I'm asking, what is the standard procedure that can take me from the recurrence relation to the closed form solution? Is there a straightforward methodology? Or is this usually done on a case-by-case basis?
-RMJ
|