Fibonacci Sequence Problem set 1

 Problems 

1. The Fibonacci numbers can be extended to zero and negative indices using the relation Fn = Fn+2 − Fn+1 . Determine F0 and find a general formula for F−n in terms of Fn. Prove your result using mathematical induction.

Solution:

F0 = F2 − F1 = 0,

F−1 = F1 − F0 = 1,

F−2 = F0 − F−1 = −1,

F−3 = F−1 − F−2 = 2,

F−4 = F−2 − F−3 = −3,

F−5 = F−3 − F−4 = 5,

F−6 = F−4 − F−5 = −8.

The correct relation appears to be

F−n = (−1)^(n+1)×Fn                .............(1)

We now prove equation (1) by mathematical induction.

Base case: Our calculation above already shows that equation (1) is true for n = 1 and n = 2, that is, F−1 = F1

and F−2 = −F2.

Induction step:

Let us  assume that (1) is true for positive integers n = k − 1 and n = k. Then we have

F−(k+1) = F−(k−1) − F(−k)     ..(from definition)

               = (−1)^k×Fk−1 − (−1)^(k+1)×Fk 

              = (−1)^(k+2)× (Fk−1 + Fk)

            = (−1)^(k+2)×Fk+1  (recursion relation)

so that (1) is true for n = k + 1. 

By the principle of induction, (1) is therefore true for all positive integers.

2.The Lucas numbers are closely related to the Fibonacci numbers and satisfy the same recursion relation Ln+1 = Ln + Ln−1, but with starting values L1 = 1 and L2 = 3. Determine the first 12 Lucas numbers.

Solution:

By using above Recursion relation one can easily obtain first 12 lucas numbers as,

1 , 3 , 4 , 7 , 11 , 18 , 29 , 47 , 76 ,123 , 199, 322.