Consider walks in the X-Y plane where each step is R: (x,y)→(x+1, y) or U: (x, y)→(x, y+a), with a a positive integer. Thereare five walks that contain a point on the line x + y = 2,namely:  RR, RU1, U1R, U1U1, and U2. Let a_n denote thenumber of walks that contain a point on the line x + y = n (so a_2= 5). Show that a_n = F_{2n}, where F_n are the Fibonacci numbersstarting with F_0 = F_1 = 1.
