Two Plus Two Newer Archives  

Go Back   Two Plus Two Newer Archives > Other Topics > Science, Math, and Philosophy

Reply
 
Thread Tools Display Modes
  #1  
Old 11-26-2007, 05:28 PM
thylacine thylacine is offline
Senior Member
 
Join Date: Jul 2003
Posts: 1,175
Default 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.
Reply With Quote
  #2  
Old 11-26-2007, 06:25 PM
gumpzilla gumpzilla is offline
Senior Member
 
Join Date: Feb 2005
Posts: 7,911
Default Re: Maths problem

I'm assuming using the Online Encyclopedia of Integer Sequences would be cheating?
Reply With Quote
  #3  
Old 11-26-2007, 07:50 PM
bigpooch bigpooch is offline
Senior Member
 
Join Date: Sep 2003
Location: Hong Kong
Posts: 1,330
Default 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>1 is real, or more simply,
b is a positive integer)?
Reply With Quote
  #4  
Old 11-26-2007, 08:07 PM
thylacine thylacine is offline
Senior Member
 
Join Date: Jul 2003
Posts: 1,175
Default 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>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.
Reply With Quote
  #5  
Old 11-26-2007, 08:10 PM
thylacine thylacine is offline
Senior Member
 
Join Date: Jul 2003
Posts: 1,175
Default 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?
Reply With Quote
  #6  
Old 11-26-2007, 08:17 PM
blah_blah blah_blah is offline
Senior Member
 
Join Date: Feb 2007
Posts: 378
Default 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
Reply With Quote
  #7  
Old 11-26-2007, 08:22 PM
borisp borisp is offline
Senior Member
 
Join Date: Nov 2004
Posts: 201
Default 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.
Reply With Quote
  #8  
Old 11-26-2007, 08:44 PM
borisp borisp is offline
Senior Member
 
Join Date: Nov 2004
Posts: 201
Default 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.)
Reply With Quote
  #9  
Old 11-26-2007, 08:49 PM
borisp borisp is offline
Senior Member
 
Join Date: Nov 2004
Posts: 201
Default 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
Reply With Quote
  #10  
Old 11-26-2007, 10:34 PM
blah_blah blah_blah is offline
Senior Member
 
Join Date: Feb 2007
Posts: 378
Default Re: Maths problem

the idea is similar to what you do with the catalan number generating function/recurrence.
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 10:23 AM.


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