online advertising

Tuesday, April 25, 2017

Negative Fibonacci Numbers

Problem:

The Fibonacci numbers can be extended to zero and negative indices using the relation $ F_n = F_{n+2}-F_{n+1} $. Determine $ F_0 $ and find a general formula for $ F_{-n} $ in terms of $ F_n $. Prove your result using mathematical induction.

Solution:

Using the usual definition of $ F_1 = F_2 = 1 $, we have $ F_0 = F_2 - F_1 = 0 $.

By cranking out some negative Fibonacci number, I propose $ F_{-n} = (-1)^{n+1} F_{n} $.

Assuming the formula is true for all number bigger than $ -n $, we have

$ \begin{eqnarray*} F_{-n} &=& F_{-n + 2} - F_{-n + 1} \\ &=& (-1)^{-n + 2 + 1} F_{n - 2} - (-1)^{-n + 1 + 1} F_{n - 1} \\ &=& (-1)^{-n + 3} F_{n - 2} - (-1)^{-n + 2} F_{n - 1} \\ &=& (-1)^{-n + 1} F_{n - 2} + (-1)^{-n + 1} F_{n - 1} \\ &=& (-1)^{-n + 1} (F_{n - 2} + F_{n - 1}) \\ &=& (-1)^{-n + 1} (F_n) \end{eqnarray*} $

So the hypothesis is proved!

No comments :

Post a Comment