# Homework Help: Finding the formula for the fibunacci sequence

1. May 16, 2010

### Susanne217

1 If I am given the function $$\frac{1}{-x^2-x+1} = \sum_{j=0}^{\infty} F_{j} x^{j}$$

Which discribes a sequence of fibunacci numbers 1,1,2,3,5,8,13,21......

Find the formula for the fibunacci sequence for n>=2 and where $$F_j = F_{j-1}+F_{j-2}$$

2. Relevant equations

3. The attempt at a solution

I know that the recusive relation can be written as $$F_j = \alpha_1(r_1)^j + \alpha_2 (r_2)^j$$

With the inital conditions $$F_0 = F_1 = 1$$

Since the poles of the function are $$r_1 = \frac{\sqrt{5}-1}{2}$$ and $$r_2 = \frac{-(\sqrt{5}+1)}{2}$$

which gives me the expression $$F_j = \alpha_1(\frac{\sqrt{5}-1}{2})^n + \alpha_2 (\frac{-(\sqrt{5}+1)}{2}})^n$$

so this gives me $$F_0 = \alpha_1 + \alpha_2 = 1$$

and $$F_1 = \alpha_1(\frac{\sqrt{5}-1}{2}) + \alpha_2 (\frac{-(\sqrt{5}+1)}{2}}) = 1$$ and I end up with

$$\alpha_1, \alpha_2 = \pm \frac{1}{\sqrt{5}}$$

and this j >= 2 then the formula for the jth fibunacci number must

$$F_j = \frac{1}{\sqrt{5}}(\frac{\sqrt{5}+1}{2})^{j+1} -\frac{1}{\sqrt{5}} (\frac{-(\sqrt{5}+1)}{2}})^{j+1}$$

How is that HallsoftIvy?

Susanne

Last edited: May 16, 2010
2. May 16, 2010

### HallsofIvy

You mean $$F_n= F_{n-1}+ F_{n-2}$$

Okay, so its just a matter of finding $$r_1$$ and $$r_2$$. If $$F_n= r^n$$ the equation $$F_n= F_{n-1}+ F_{n-2}$$ becomes $$r^n= r^{n-1}+ r^{n-2}$$. Dividing that equation by $$r^{n-1}$$ gives $$r^2= r+ 1$$. What are the roots of that equation?

No fair! You edited and added your solution while I was responding!

3. May 16, 2010

### Susanne217

Sorry HallsoftIvy :)