Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Reply
 
Thread Tools Display Modes
  #1  
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?

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
Reply With Quote
  #2  
Old 09-19-2005, 06:03 PM
Guest
 
Posts: n/a
Default 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.
Reply With Quote
  #3  
Old 09-20-2005, 02:51 AM
pzhon pzhon is offline
Member
 
Join Date: Mar 2004
Posts: 66
Default 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.
Reply With Quote
  #4  
Old 09-20-2005, 04:05 PM
alThor alThor is offline
Junior Member
 
Join Date: Mar 2004
Posts: 6
Default 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
Reply With Quote
  #5  
Old 09-20-2005, 06:02 PM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default 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)*...).
Reply With Quote
  #6  
Old 09-21-2005, 06:25 PM
AaronBrown AaronBrown is offline
Senior Member
 
Join Date: May 2005
Location: New York
Posts: 505
Default 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.
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 11:24 PM.


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