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 $f_{n}= f_{n+2} - f_{n+1}$ is perfectly possible. Starting with $f_{1}=f_{0}=1$ we obtain...

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

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

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

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

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

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

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

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

$\dots$

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

Kind regards

$\chi$ $\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 $f_n=f_{n-1}+f_{n-2}$. This is a homogenous linear recurrence relation. That said, it's solution is of the form $f_n=C_1 \alpha^n+C_2 \beta^n$. Where $\alpha,\beta$ are the solutions the auxiliary polynomial $x^2-x-1=0$ and $C_1,C_2$ are determined by initial conditions.

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

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

,

,

,

,

negative fibonacci numbers

Click on a term to search for related topics.