View Full Version : Recurrence Relation to Closed Form
RocketManJames
09-19-2005, 04:52 PM
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
There is no general tool for recurrance relations like that.
In your case we have:
F(n)=product from {i=1} to n of (2i-1)(i)
F(n)=1/2^n product from {i=1} to n of (2i-1)(2i)
F(n)=1/2^n product from {i=1} to 2n of (i)
F(n)=1/2^n (2n)!
That said, I haven't the foggiest if I would have been able to do that without seeing your 'closed form' version. Notably, n! is generally not really a closed form sort of thing unless you're using something like stirling's approximation.
pzhon
09-20-2005, 02:51 AM
[ QUOTE ]
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?
[/ QUOTE ]
I believe there are straightforward methods that work for examples as simple as this, but these are also usually done individually.
This is an example of a hypergeometric (http://mathworld.wolfram.com/HypergeometricSeries.html) sequence.
alThor
09-20-2005, 04:05 PM
[ QUOTE ]
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?
[/ QUOTE ]
Given the recurrence, start at n=0 (or =1, or whatever is appropriate for the problem) and write out the values of f(n) only as a function of n (i.e. substituting the value of f(n-1) appropriately) and look for a pattern. This can take a lot of paper, and might not work in all cases. Then try to prove your pattern inductively: assume it's true for n-1, prove it for n. Other than that, yes it's case-by-case.
You are, presumably, initializing f(1) = 1.
Then
f(2) = [1] [(3)(4)/2]
f(3) = [1] [(3)(4)/2] [(5)(6)/2]
f(4) = [1] [(3)(4)/2] [(5)(6)/2] [(7)(8)/2]
...
Look how clear it is that you are multiplying all the numbers 3,4,5,6,7,8,etc. Clean it up by throwing in a 2/2 term in front, and you have (2n)! practically jumping off the page at you. Even easier is the 1/2^n factor. You're done.
alThor
irchans
09-20-2005, 06:02 PM
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)*...).
AaronBrown
09-21-2005, 06:25 PM
Another useful technique is to use Excel to see the first 10 values, and see if any pattern emerges. With a little practice you can easily spot patterns for many simple formulae.
vBulletin® v3.8.11, Copyright ©2000-2024, vBulletin Solutions Inc.