Answer Happy

Let n denote a positive integer, and consider an n by n chessboard. A cricket starts at the top left square and ends up at the bottom right square, after 2n hops. Each hop takes the cricket from a given square to an adjacent square to the east or south. The cricket hops at random, and each path of length 2n from the top left square to the bottom right square is equally likely. Let Pn denote the probability that the cricket stays on or above the main diagonal throughout its trip. (i) (3 points) Find P1, P2, P3- (ii) (3 points) Express Pn in closed form. (iii) (4 points) Prove that your answer to (ii) is correct for all n.