## 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!