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.

Re: Maths problem
 

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

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

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.

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?

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

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.

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

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

Re: Maths problem
 

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

Re: Maths problem
 

[ 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 [img]/images/graemlins/smile.gif[/img]...haven't done this since undergrad.

Re: Maths problem
 

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

Re: Maths problem
 

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

Re: Maths problem
 

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

Re: Maths problem
 

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

Re: Maths problem
 

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

Re: Maths problem
 

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

Re: Maths problem
 

you may find the discussion here interesting

http://www.artofproblemsolving.com/F...00&t=40150

Re: Maths problem
 

[ QUOTE ]
you may find the discussion here interesting

http://www.artofproblemsolving.com/F...00&t=40150

[/ QUOTE ]

link didn't work

Re: Maths problem
 

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 .

Re: Maths problem
 

One important detail I left out .

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

Re: Maths problem
 

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

Re: Maths problem
 

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

Re: Maths problem
 

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

http://www.artofproblemsolving.com/F...00&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?

Re: Maths problem
 

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

[/ QUOTE ]

one and the same