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
|
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 |
All times are GMT -4. The time now is 10:19 AM. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.