|
#1
|
|||
|
|||
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.) |
#2
|
|||
|
|||
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 |
#3
|
|||
|
|||
Re: Maths problem
the idea is similar to what you do with the catalan number generating function/recurrence.
|
#4
|
|||
|
|||
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. |
#5
|
|||
|
|||
Re: Maths problem
idk, i too am an analyst (well, more of a probabilist these days ... but close enough)
|
#6
|
|||
|
|||
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. |
#7
|
|||
|
|||
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). |
#8
|
|||
|
|||
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. |
#9
|
|||
|
|||
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 |
#10
|
|||
|
|||
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. |
|
|