Two Plus Two Newer Archives Maths problem
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#1
11-26-2007, 05:28 PM
 thylacine Senior Member Join Date: Jul 2003 Posts: 1,175
Maths problem

Find a formula for f(n) (n=0,1,2,3,...) where

f(0)=1

f(0)f(n)+f(1)f(n-1)+...+f(n-1)f(1)+f(n)f(0)=4^n for n=0,1,2,3,...

that is, \sum_{i=0}^{n} f(i)f(n-i)=4^n for n=0,1,2,3,...

No need to post solutions in white. I am interested to see what different techniques people come up with, and what form they write f(n) in.
#2
11-26-2007, 06:25 PM
 gumpzilla Senior Member Join Date: Feb 2005 Posts: 7,911
Re: Maths problem

I'm assuming using the Online Encyclopedia of Integer Sequences would be cheating?
#3
11-26-2007, 07:50 PM
 bigpooch Senior Member Join Date: Sep 2003 Location: Hong Kong Posts: 1,330
Re: Maths problem

For the RHS of the recurrence is 4^n, the solution is
combinatorial. Are you suggesting techniques or methods
that are useful in the general case: where the RHS = g(n)
(even simply if g(n)=b^n where b&gt;1 is real, or more simply,
b is a positive integer)?
#4
11-26-2007, 08:07 PM
 thylacine Senior Member Join Date: Jul 2003 Posts: 1,175
Re: Maths problem

[ QUOTE ]
For the RHS of the recurrence is 4^n, the solution is
combinatorial. Are you suggesting techniques or methods
that are useful in the general case: where the RHS = g(n)
(even simply if g(n)=b^n where b&gt;1 is real, or more simply,
b is a positive integer)?

[/ QUOTE ]

Anything you like. Any level of generality is of interest, since you may be able to say more in the more special cases.
#5
11-26-2007, 08:10 PM
 thylacine Senior Member Join Date: Jul 2003 Posts: 1,175
Re: Maths problem

[ QUOTE ]
I'm assuming using the Online Encyclopedia of Integer Sequences would be cheating?

[/ QUOTE ]

I've never looked at this or thought about it. How would you use it?
#6
11-26-2007, 08:17 PM
 blah_blah Senior Member Join Date: Feb 2007 Posts: 378
Re: Maths problem

use a computer or pencil and paper to compute the first ten or so numbers. plug it in to the OEIS. the OEIS may give you one or more of the following

1) references
2) equivalences between related problems (which you may know how to solve)
3) closed form (which you probably can then verify by induction or whatever)
4) the appropriate generating function
#7
11-26-2007, 08:22 PM
 borisp Senior Member Join Date: Nov 2004 Posts: 201
Re: Maths problem

Is the answer 2n choose n? That's the pattern I found after a few minutes of doodling. I assume that an induction could prove this, although it would be messy. Of course, it might not be right, which is why I'm asking rather than wasting time.

I did try to prove this combinatorially; the RHS of the defining relation is the number of subsets of {1,2,...,2n}, or equivalently the number of pairs of subsets of {1,2,...,n}. Reinterpreting the LHS could lead to a combinatorial proof, but I haven't found one after some trying, and I need to get back to real work, so I give up.
#8
11-26-2007, 08:44 PM
 borisp Senior Member Join Date: Nov 2004 Posts: 201
Re: Maths problem

[ QUOTE ]
the appropriate generating function

[/ QUOTE ]
ahhh, this is how to do it. The relation asks for a square root of the generating function 1+4x+16x^2+...=1/(1-4x). So use binomial coefficients to compute the nth coefficient of (1-4x)^(-1/2), and that should be the answer. (I haven't actually done this, but it should work out.)
#9
11-26-2007, 08:49 PM
 borisp Senior Member Join Date: Nov 2004 Posts: 201
Re: Maths problem

Ok, so to hell with real work: the nth coeffcient is

4^n(1/2 choose n) = (4^n/2^n) ((1*3*5*...*2n-1)/n!)=

=2^n*((2n!)/((2n)*(2n-2)*...*(4)*(2)*n!)=(2^n/2^n)(2n!/(n!n!))=

= 2n choose n
#10
11-26-2007, 10:34 PM
 blah_blah Senior Member Join Date: Feb 2007 Posts: 378
Re: Maths problem

the idea is similar to what you do with the catalan number generating function/recurrence.

 Thread Tools Display Modes Linear 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     The Two Plus Two Bonus Program     Special Sklansky Forum     About the Forums     MOD DISCUSSION     Test General Poker Discussion     Beginners Questions     Books and Publications     Televised Poker     News, Views, and Gossip     Brick and Mortar     Home Poker     Poker Beats, Brags, and Variance     Poker Theory     Poker Legislation Coaching/Training     Stoxpoker.com     DeucesCracked.com German Forums     Poker Allgemein: Poker in general     Strategie: Holdem NL cash [German]     Strategie: Sonstige     Internet/Online [German]     BBV [German]     Small Talk [German] French Forums     Forum Francophone     Strategie [French]     BBV [French] Limit Texas Hold'em     Texas Hold'em     High Stakes Limit     Medium Stakes Limit     Small Stakes Limit     Micro Stakes Limit     Mid-High Stakes Shorthanded     Small Stakes Shorthanded     Limit-->NL PL/NL Texas Hold'em     High Stakes     Medium Stakes     Small Stakes     Micro Stakes     Full Ring Tournament Poker     MTT Strategy     High Stakes MTT     MTT Community     STT Strategy     Tournament Circuit/WSOP Other Poker     Omaha/8     Omaha High     Stud     Heads Up Poker     Other Poker Games General Gambling     Probability     Psychology     Sports Betting     Other Gambling Games     Entertainment Betting     Money Making and Other Business Discussion Internet Gambling     Internet Gambling     Internet Bonuses     Affiliates/RakeBack     Software     Poker Site Software, Skins, & Networks 2+2 Communities     Other Other Topics     The Lounge: Discussion+Review     EDF     BBV4Life Other Topics     Sporting Events     Politics     Business, Finance, and Investing     Travel     Science, Math, and Philosophy     Health and Fitness     Student Life     Golf     Video Games     Puzzles and Other Games     Laughs or Links!     Computer Technical Help     Bin Sponsored Support Forums     RakebackNetwork     RakeBackDepot     RakeReduction.com Rakeback     PokerSavvy

All times are GMT -4. The time now is 09:55 AM.