Two Plus Two Older Archives Recurrence Relation to Closed Form
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#1
09-19-2005, 04:52 PM
 RocketManJames Senior Member Join Date: Nov 2002 Posts: 118
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
09-19-2005, 06:03 PM
 Guest Posts: n/a
Re: Recurrence Relation to Closed Form

There is no general tool for recurrance relations like that.

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
09-20-2005, 02:51 AM
 pzhon Member Join Date: Mar 2004 Posts: 66
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
09-20-2005, 04:05 PM
 alThor Junior Member Join Date: Mar 2004 Posts: 6
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
09-20-2005, 06:02 PM
 irchans Senior Member Join Date: Sep 2002 Posts: 157
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
09-21-2005, 06:25 PM
 AaronBrown Senior Member Join Date: May 2005 Location: New York Posts: 505
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.

 Thread Tools Display Modes Hybrid Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Two Plus Two     Two Plus Two Internet Magazine     About the Forums     MOD DISCUSSION     ISOP General Poker Discussion     Texas Hold'em     Beginners Questions     Books and Publications     Televised Poker     News, Views, and Gossip     Brick and Mortar     Home Poker     Poker Beats, Brags, and Variance     Poker Theory Limit Texas Hold'em     Mid- and High-Stakes Hold'em     Medium Stakes Hold'em     Small Stakes Hold'em     Micro-Limits     Mid-High Stakes Shorthanded     Small Stakes Shorthanded PL/NL Texas Hold'em     Mid-, High-Stakes Pot- and No-Limit Hold'em     Medium-Stakes Pot-, No-Limit Hold'em     Small Stakes Pot-, No-Limit Hold'em Tournament Poker     Multi-table Tournaments     One-table Tournaments Other Poker     Omaha/8     Omaha High     Stud     Other Poker Games General Gambling     Probability     Psychology     Sports Betting     Other Gambling Games     Rake Back     Computer Technical Help Internet Gambling     Internet Gambling     Internet Bonuses     Software 2+2 Communities     Other Other Topics Other Topics     Sporting Events     Politics     Science, Math, and Philosophy     The Stock Market

All times are GMT -4. The time now is 06:21 PM.