Derivation of nth fibonacci term

[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),
and how was this derived

 

[HallsofIvy]

The Fibonacci sequence is defined by F₀= 1, F₁= 1, F_n+2= F_n+1+ F_n.

A standard method of trying to solve such recursion formulas is to try something of the form F_n= aⁿ. Then, of course, F_n+1= aⁿ⁺¹ and F_n+2= aⁿ⁺² so the equation becomes aⁿ⁺²= aⁿ⁺¹+ aⁿ. If we divide the entire equation by aⁿ we arrive at a²= a+ 1 or the quadratic equation a²- 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
[tex]F_0= A+ B= 1[/itex]
and, if n= 1
$$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.

 

[soandos]

Thank you!

 

[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.

 

[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}}$$

 

[Integral]

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.

 

[HallsofIvy]

Dang! If I could only do arithmetic!

 

[Integral]

Dang! If I could only do arithmetic!

How well I know the feeling.

 

[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.

 

[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.

 

[Borek]

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.

 

[Coin]

$$\frac{1\plus\sqrt{5}}{2}$$

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?