Maths problem

[thylacine]

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.

[gumpzilla]

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

[bigpooch]

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)?

[thylacine]

[ 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.

[thylacine]

[ 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?

[blah_blah]

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

[borisp]

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.

[borisp]

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

[borisp]

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

[blah_blah]

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