|
#1
|
|||
|
|||
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 |
#2
|
|||
|
|||
Re: Recurrence Relation to Closed Form
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. |
#3
|
|||
|
|||
Re: Recurrence Relation to Closed Form
[ 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 sequence. |
#4
|
|||
|
|||
Re: Recurrence Relation to Closed Form
[ 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 |
#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)*...). |
#6
|
|||
|
|||
Re: Recurrence Relation to Closed Form
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.
|
|
|