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.

[borisp]

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

[/ QUOTE ]
The catalan generating function would be the integral of this function, divided by x. Is there a nice combinatorial interpretation of derivatives and integrals of generating functions?

Forgive me, I am an analyst /images/graemlins/smile.gif...haven't done this since undergrad.

[blah_blah]

idk, i too am an analyst (well, more of a probabilist these days ... but close enough)

[thylacine]

[ QUOTE ]
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

[/ QUOTE ]

There are some sign errors here.
Rough idea is right.

[borisp]

I left out the signs because they become +1 in the end. The (-1)^n from the -4 and the (-1)^n from the -1/2 join forces to become (-1)^2n = +1.

So there really aren't any sign errors, in that the result is correct. I was just lazy with the typing. Technically the first term should be (-4)^n*(-1/2 choose n).

[thylacine]

[ QUOTE ]
I left out the signs because they become +1 in the end. The (-1)^n from the -4 and the (-1)^n from the -1/2 join forces to become (-1)^2n = +1.

So there really aren't any sign errors, in that the result is correct. I was just lazy with the typing. Technically the first term should be (-4)^n*(-1/2 choose n).

[/ QUOTE ]

No. (-1)^n (r choose n) does not equal (-r choose n). You can figure out what it does equal.

You are right that the first term should be (-4)^n*(-1/2 choose n).

You essentially got the solution I was thinking of. I was interested if there were any other approaches.

[jay_shark]

Has anyone thought of a combinatorial solution to this ?
I have tried and failed .

We wish to prove :

2nCn + 2c1*(2n-2)C(n-1) + 4c2*(2n-4)C(n-2) + ...+ 2nCn = 4^n

[thylacine]

[ QUOTE ]
Has anyone thought of a combinatorial solution to this ?
I have tried and failed .

We wish to prove :

2nCn + 2c1*(2n-2)C(n-1) + 4c2*(2n-4)C(n-2) + ...+ 2nCn = 4^n

[/ QUOTE ]

I don't know of one. I was thinking of the generating function method. But it would be interesting to know.

[blah_blah]

you may find the discussion here interesting

http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1693682000&t=40150

[thylacine]

[ QUOTE ]
you may find the discussion here interesting

http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1693682000&t=40150

[/ QUOTE ]

link didn't work

[jay_shark]

Here is a neat combinatorial argument .

Start from the origin and consider taking 2n steps on the lattice points of the line y=x or y=-x . Clearly the total number of paths is 2^(2n) . The number of ways of reaching the point (2n,0) is 2nCn . It is also true that the number of paths that do not intersect the x-axis is 2nCn . Since we can reflect all subsequent paths after the first step in the line y=1 or -1 to produce a bijection of paths that do not intersect the x-axis .

Consider the last path that intersects the x-axis at the points (2k,0) . The number of paths is 2kCk . Therefore we require the last (2n-2k) to be above or below the x-axis . The total number of ways is equal to the number of ways of reaching the point (2n,0) which is just (2n-2k)C(n-k) . Now sum over everything and we get our identity .

[jay_shark]

One important detail I left out .

We move in the direction up-right or down-right .

[TWCReborn]

To the original poster: Was this a homework problem in a combinatorics class? Just curious.

[thylacine]

[ QUOTE ]
To the original poster: Was this a homework problem in a combinatorics class? Just curious.

[/ QUOTE ]

I made it up, but I'm sure this exact problem has been `made up' many times before. As above posters noted, it's closely related to generating function stuff for Catalan numbers.

[thylacine]

[ QUOTE ]
[ QUOTE ]
you may find the discussion here interesting

http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1693682000&t=40150

[/ QUOTE ]

link didn't work

[/ QUOTE ]

Nevermind, I tried it again and it worked this time (my crappy connection). Obviously this is an old maths problem as I suspected.

Hey blah_blah, I don't suppose that you are blahblahblah on that site you link?

[blah_blah]

[ QUOTE ]
Hey blah_blah, I don't suppose that you are blahblahblah on that site you link?

[/ QUOTE ]

one and the same