|
#1
|
|||
|
|||
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. |
#2
|
|||
|
|||
Re: Maths problem
|
#3
|
|||
|
|||
Re: Maths problem
[ QUOTE ]
you may find the discussion here interesting http://www.artofproblemsolving.com/F...00&t=40150 [/ QUOTE ] link didn't work |
#4
|
|||
|
|||
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 . |
#5
|
|||
|
|||
Re: Maths problem
One important detail I left out .
We move in the direction up-right or down-right . |
#6
|
|||
|
|||
Re: Maths problem
To the original poster: Was this a homework problem in a combinatorics class? Just curious.
|
#7
|
|||
|
|||
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. |
#8
|
|||
|
|||
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? |
#9
|
|||
|
|||
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 |
|
|