PDA

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

09-19-2005, 06:03 PM
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) =  [(3)(4)/2]
f(3) =  [(3)(4)/2] [(5)(6)/2]
f(4) =  [(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.