Maths problem

[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 .