# Derivation of nth fibonacci term

1. Aug 31, 2008

### soandos

i know that there is a formula to find the nth term.
two questions:

what does mean for non-integer n (as the recurrence relation breaks down i think),

2. Sep 1, 2008

### HallsofIvy

Staff Emeritus
The Fibonacci sequence is defined by F0= 1, F1= 1, Fn+2= Fn+1+ Fn.

A standard method of trying to solve such recursion formulas is to try something of the form Fn= an. Then, of course, Fn+1= an+1 and Fn+2= an+2 so the equation becomes an+2= an+1+ an. If we divide the entire equation by an we arrive at a2= a+ 1 or the quadratic equation a2- a- 1= 0. Solving that by the quadratic formula,
$$a= \frac{1\pm\sqrt{5}}{2}$$
That tells us that
$$F_n= \left(\frac{1+ \sqrt{5}}{2}\right)^n$$
and
$$F_n= \left(\frac{1-\sqrt{5}}{2}\right)^n$$
satisfy that equation. Since this is a linear equation, any solution must be of the form
$$F_n= A\left(\frac{1+ \sqrt{5}}{2}\right)^n+ B\left(\frac{1- \sqrt{5}}{2}\right)^n$$
for some numbers A and B.
In particular, if n= 0
$$F_0= A+ B= 1[/itex] and, if n= 1 [tex]F_n= A\left(\frac{1+ \sqrt{5}}{2}\right)+ B\left(\frac{1- \sqrt{5}}{2}\right)= 1$$
Solving those two equations for A and B, we get (assuming I have done the arithmetic correctly!)
$$A= \frac{1+\sqrt{5}}{2\sqrt{5}}$$
and
$$B= \frac{1-\sqrt{5}}{2\sqrt{5}}$$

Putting all of that together, we have
$$F_n= \frac{1+\sqrt{5}}{2\sqrt{5}}\left(\frac{1+ \sqrt{5}}{2}\right)^n+ \frac{1-\sqrt{5}}{2\sqrt{5}}\left(\frac{1- \sqrt{5}}{2}\right)^n$$

It is remarkable that this gives integer values for n any non-negative integer!

I don't know that it "means" anything for non-integer n.

3. Sep 1, 2008

Thank you!

4. Sep 1, 2008

### Staff: Mentor

I wonder if using formula shown by HallsofIvy is faster than using definition, as raising irrational numbers to high powers with high accuracy is numerically much more expensive then integer addition.

5. Sep 1, 2008

### robert Ihnot

I don't see how that formula works. It does not work for n=1. I take this, as well as I can write it, to be the standard form:

$$((\frac{1+\sqrt5}{2}})^n-({\frac{1-\sqrt5}{2})^n})*{\frac{1}{\sqrt5}}$$

Last edited: Sep 1, 2008
6. Sep 2, 2008

### Integral

Staff Emeritus
Halls,
I think you lost a minus sign on the B term should read:

$$F_n= \frac{1+\sqrt{5}}{2\sqrt{5}}\left(\frac{1+ \sqrt{5}}{2}\right)^n- \frac{1-\sqrt{5}}{2\sqrt{5}}\left(\frac{1- \sqrt{5}}{2}\right)^n$$

Edit may as well finish it.

This can be written as:

$$F_n = \left(\left(\frac {1+ \sqrt{5}} 2\right)^{n+1} - \left (\frac {1- \sqrt{5}} 2\right)^{n+1} \right)* \frac 1 {\sqrt{5}}$$

Edit again:
Robert, you seem to have lost a factor, your exponent should be n+1, it does indeed work with that correction.

Last edited: Sep 2, 2008
7. Sep 2, 2008

### HallsofIvy

Staff Emeritus
Dang! If I could only do arithmetic!

8. Sep 2, 2008

### Integral

Staff Emeritus
:rofl: How well I know the feeling.

9. Sep 2, 2008

### robert Ihnot

Integral, Robert, you seem to have lost a factor, your exponent should be n+1, it does indeed work with that correction.

It depends upon how we start the series. Wolfram says, F(1) = F(2) = 1.
http://mathworld.wolfram.com/FibonacciNumber.html.

10. Sep 2, 2008

### robert Ihnot

Borek: I wonder if using formula shown by HallsofIvy is faster than using definition, as raising irrational numbers to high powers with high accuracy is numerically much more expensive then integer addition.

One thing that happens here is that the second term goes to zero. Even using this term: $$(-\frac{1-\sqrt5}{2})^3*(\frac{1}{\sqrt5}) = \succ.11$$ (Approximately .11)

So that we only need to use the closest interger to the first term.

11. Sep 3, 2008

### Staff: Mentor

It doesn't change much. It is still about log(n) multiplications to calculate nth power. In the end we have n integer additions vs log(n) real multiplications. Or something like that.

12. Sep 3, 2008

### Coin

Hey, whoa, it's the golden ratio! Is the way that the golden ratio shows up in your derived formula something that is something special about the Fibonacci sequence compared to other recursive formulas?