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. There
are five walks that contain a point on the line x + y = 2,
namely: RR, RU1, U1R, U1U1, and U2. Let a_n denote the
number 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 numbers...