Question

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 starting with F_0 = F_1 = 1.

Answer 1

Here we have to show that a_n=F_F2

PROOF --

Suppose W(n) is the set of walks that contain a point on the line given by following equation

x + y = n. For X ∈ {R, U}
and also , let W(n, X) be the set of walks that contain a point on the line x + y = n and start with X
Now We may extend a walk w ∈ W(n−1) to a walk in W(n) that contains a point on the line x+y = n in different ways defined as following types

(1) if w ∈ W(n − 1, U) then we may append R or U1 to the beginning of w or increase the number following the first U by 1 and
(2) if w ∈ W(n − 1, R) then we may append R or U1 to the beginning of w.
Next, on observing all the walks that are contracted by the above method are distinct (consider its first 2 steps) and contain the point on the line given by equation x + y = n. In addition all the walks that contain a point on the line given by the equation x + y = n can be generated by the method given above .

Therefore
|W(n)| = 3|W(n − 1, U)| + 2|W(n − 1, R)| = 3|W(n − 1)| − |W(n − 1, R)|.
If w ∈ W(n − 1, R) then by removing the first step of w we will get a walk in W(n − 2).

Similarly
if w ∈ W(n − 2) we may generate a walk in W(n − 1, R) by appending an R to its beginning.
So ,we have

|W(n − 1, R)| = |W(n − 2)|

and also
a_n= |W(n)| = 3|W(n − 1)| − |W(n − 2)| = 3a_n-1 -a_n-1 ............equation(1)

The same recurrence as equation (1) is satisfied by the sequence {F2n}_n∈​​​_Z≥0

where F_2n =  (2n)^th  Fibonacci number.
now ,

F_2n = F_2n-1 + F_2n-2 = 2F_2n-2 + F_2n-3
= 3F_2n-2  − (F_2n-3 + F_2n-4) + F_2n-3

= 3F_2n-2− F_2n-4
we get the sequences {a_n}n∈Z≥0 , {F_2n}n∈Z≥0 satisfy the same recurrent, a0 = F0 = 1, a1 = F2·1 = 2 and a2 = F2·2 = 5 .

So we can conclude from above result that
a_n= F_{2n ,} for n ≥ 0.

Hence proved

Please like??