# Thread: Fibonacci numbers with negative indices

1. ## Fibonacci numbers with negative indices

Let the Fibonacci sequence Fn be defined by its recurrence relation (1) Fn=F(n-1)+F(n-2) for n>=3. Show that there is a unique way to extend the definition of Fn to integers n<=0 such that (1) holds for all integers n, and obtain an explicit formula for the terms Fn with negative indices n.

I am completely stuck on how to prove this by induction. I figured that Fn = Fn+2-Fn+1, but i don't know how to apply induction to this to prove it for all integers n

2. The recursive computation $\displaystyle f_{n}= f_{n+2} - f_{n+1}$ is perfectly possible. Starting with $\displaystyle f_{1}=f_{0}=1$ we obtain...

$\displaystyle f_{-1} = f_{1} - f_{0} = 0$

$\displaystyle f_{-2} = f_{0} - f_{-1} = 1$

$\displaystyle f_{-3} = f_{-1} - f_{-2} = -1$

$\displaystyle f_{-4} = f_{-2} - f_{-3} = 2$

$\displaystyle f_{-5} = f_{-3} - f_{-4} = -3$

$\displaystyle f_{-6} = f_{-4} - f_{-5} = 5$

$\displaystyle f_{-7} = f_{-5} - f_{-6} = -8$

$\displaystyle f_{-8} = f_{-6} - f_{-7} = 13$

$\displaystyle \dots$

It seems that the 'negative sequence' replies, with alternating signs, the 'positive sequence'...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

3. Thanks Chisigma! But how would one prove this using induction? Thats the part that really bugs me.

4. Originally Posted by morbius27
Let the Fibonacci sequence Fn be defined by its recurrence relation (1) Fn=F(n-1)+F(n-2) for n>=3. Show that there is a unique way to extend the definition of Fn to integers n<=0 such that (1) holds for all integers n, and obtain an explicit formula for the terms Fn with negative indices n.

I am completely stuck on how to prove this by induction. I figured that Fn = Fn+2-Fn+1, but i don't know how to apply induction to this to prove it for all integers n
You have that $\displaystyle f_n=f_{n-1}+f_{n-2}$. This is a homogenous linear recurrence relation. That said, it's solution is of the form $\displaystyle f_n=C_1 \alpha^n+C_2 \beta^n$. Where $\displaystyle \alpha,\beta$ are the solutions the auxiliary polynomial $\displaystyle x^2-x-1=0$ and $\displaystyle C_1,C_2$ are determined by initial conditions.

It turns out that $\displaystyle f_n=\frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}}$ where $\displaystyle \varphi$ is the golden ratio.

This is clearly a canonical way to extend $\displaystyle f_n$ to $\displaystyle \mathbb{Z}$

,

,

,

,

### negative fibonacci numbers

Click on a term to search for related topics.