Two Plus Two Older Archives (http://archives2.twoplustwo.com/index.php)
-   Probability (http://archives2.twoplustwo.com/forumdisplay.php?f=23)
-   -   Recurrence Relation to Closed Form (http://archives2.twoplustwo.com/showthread.php?t=340145)

 RocketManJames 09-19-2005 04:52 PM

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

 09-19-2005 06:03 PM

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.

 pzhon 09-20-2005 02:51 AM

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.

 alThor 09-20-2005 04:05 PM

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) =  [(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

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)*...).

 AaronBrown 09-21-2005 06:25 PM

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.

 All times are GMT -4. The time now is 05:37 PM.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.