View Single Post
Old 09-19-2005, 04:52 PM
RocketManJames RocketManJames is offline
Senior Member
Join Date: Nov 2002
Posts: 118
Default 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?


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?

Reply With Quote