Maths problem

[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 [img]/images/graemlins/smile.gif[/img]...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/F...00&t=40150

[thylacine]

[ QUOTE ]
you may find the discussion here interesting

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