Subcontests
(3)Lattice points and path
Let X be the set of all lattice points in the plane (points (x,y) with x,y∈Z). A path of length n is a chain (P0,P1,...,Pn) of points in X such that Pi−1Pi=1 for i=1,...,n. Let F(n) be the number of distinct paths beginning in P0=(0,0) and ending in any point Pn on line y=0. Prove that F(n)=(n2n)