Lemma 2 If n is a positive integer, then an = Fn+1.
Proof. We have a1 = 1 = F2, a2 = 2 = F3, and the same recurrent formula
eects for both sequences fang1 n=1 and fFng1 n=1, so an = Fn+1.
Now let us prove the following formula for a Fibonacci number with an odd
index.