Two Plus Two Newer Archives  

Go Back   Two Plus Two Newer Archives > Other Topics > Science, Math, and Philosophy

Reply
 
Thread Tools Display Modes
  #11  
Old 11-27-2007, 07:05 AM
borisp borisp is offline
Senior Member
 
Join Date: Nov 2004
Posts: 201
Default 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.
Reply With Quote
  #12  
Old 11-27-2007, 07:50 AM
blah_blah blah_blah is offline
Senior Member
 
Join Date: Feb 2007
Posts: 378
Default Re: Maths problem

idk, i too am an analyst (well, more of a probabilist these days ... but close enough)
Reply With Quote
  #13  
Old 11-27-2007, 09:41 PM
thylacine thylacine is offline
Senior Member
 
Join Date: Jul 2003
Posts: 1,175
Default 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.
Reply With Quote
  #14  
Old 11-27-2007, 11:26 PM
borisp borisp is offline
Senior Member
 
Join Date: Nov 2004
Posts: 201
Default 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).
Reply With Quote
  #15  
Old 11-27-2007, 11:53 PM
thylacine thylacine is offline
Senior Member
 
Join Date: Jul 2003
Posts: 1,175
Default 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.
Reply With Quote
  #16  
Old 11-28-2007, 11:01 PM
jay_shark jay_shark is offline
Senior Member
 
Join Date: Sep 2006
Posts: 2,277
Default 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
Reply With Quote
  #17  
Old 11-29-2007, 04:41 PM
thylacine thylacine is offline
Senior Member
 
Join Date: Jul 2003
Posts: 1,175
Default 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.
Reply With Quote
  #18  
Old 11-29-2007, 05:12 PM
blah_blah blah_blah is offline
Senior Member
 
Join Date: Feb 2007
Posts: 378
Default Re: Maths problem

you may find the discussion here interesting

http://www.artofproblemsolving.com/F...00&t=40150
Reply With Quote
  #19  
Old 11-29-2007, 06:51 PM
thylacine thylacine is offline
Senior Member
 
Join Date: Jul 2003
Posts: 1,175
Default Re: Maths problem

[ QUOTE ]
you may find the discussion here interesting

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

[/ QUOTE ]

link didn't work
Reply With Quote
  #20  
Old 11-29-2007, 08:09 PM
jay_shark jay_shark is offline
Senior Member
 
Join Date: Sep 2006
Posts: 2,277
Default 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 .
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 10:19 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.