I am proving the part 1 of the problem only.
Without any restriction the number of paths from (0,0) to (n,n) is 2nCn.
Now,our problem has a restriction that we cannot cross the x=y line.
So, out of 2nCn paths we have to substract those paths which crosses the x=y line.
Now, I am going to prove that the no. of paths which crosses the x=y line is equal to number of paths we can take to go from (0,0) to (n-1,n+1).
Look at the above image I have taken n=3 for simplicity. Assume there is one black ant and one red ant at the point (0,0). Now, the red ant wants to reach the point (2,4) and the black ant wants to reach the point (3,3).
The red ant can move only in the red region (shaded with red pen) and the black ant moves only in the black region (shaded with black pen) and suppose the black ant has sworn that it will take at least one point above the x=y line during his journey.
Note that red ant has to take at least one point above x=y line because the point (2,4) is above x=y line.
Now, to prove the number of paths can be taken by the red ant to reach the point (2,4) = number of path can be taken by the black ant to reach (3,3)
When the ants are moving through their common region ( the square (0,0) (2,0) (2,3) (0,3) ) they are moving together problem occurs when one ant leaves the common region.
Take a path traced by the black ant HHUUUH
Now, since the red ant is moving together with the black ant when they are in the common region so, the path traced by the red ant upto the point (2,3) (note that the black ant reaches the point (2,3) in the above given path) is HHUUU
Now, the problem occurs when black ant goes horizontal to the point (3,3) then the red ant would take an upward direction to (2,4)
Whenever the black ant leaves the common region the red ant takes a path towards upward direction and after that follows the same direction as black ant.
Take another path for black ant HUUHHU the corresponding path for red ant will be HUUHUU.
In this way we will get an unique path for red ant corresponding to the path taken by the black ant.
Similarly we will also get an unquie path for black ant corresponding to a path taken by a red ant.(Think)
Thus set of paths taken by the red ant forms a bijective mapping with the set of paths taken by the black ant where at least one point is above the x=y line.
So, the number of paths taken by the black ant by taking at least one point above the x=y line = the no. of paths taken by the red ant to reach the point (2,4) = 6C2
In general it will be 2nCn-1
So, our required result is 2nCn - 2nCn-1 ( part 1 of the problem proved ).