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 ...