Donations are essential to keep Write Out Loud going    

part of the sequence of the equation for scratching my nose...

Closed form expression

Like every sequence defined by linear recurrence, the Fibonacci numbers have a closed-form solution. It has become known as Binet's formula, even though it was already known by Abraham de Moivre:

Fleft(n
ight) = {{varphi^n-(1-varphi)^n} over {sqrt 5}}={{varphi^n-(-1/varphi)^{n}} over {sqrt 5}}, , where varphi, is the golden ratio
varphi = (sequence A001622 in OEIS)

(note, that 1-varphi=-1/varphi, as can be seen from the defining equation above).

The Fibonacci recursion

F(n+2)-F(n+1)-F(n)=0,

is similar to the defining equation of the golden ratio in the form

x^2-x-1=0,,

which is also known as the generating polynomial of the recursion.

[edit] Proof by induction

Any root of the equation above satisfies and multiplying by x^{n-1}, shows:

x^{n+1} = x^n + x^{n-1},

By definition varphi, is a root of the equation, and the other root is 1-varphi,=-1 / varphi, . Therefore:

varphi^{n+1}  = varphi^n + varphi^{n-1},

and

(1-varphi)^{n+1} = (1-varphi)^n + (1-varphi)^{n-1}, .

Both varphi^{n} and (1-varphi)^{n}=(-1/varphi)^{n} are geometric series (for n = 1, 2, 3, ...) that satisfy the Fibonacci recursion. The first series grows exponentially; the second exponentially tends to zero, with alternating signs. Because the Fibonacci recursion is linear, any linear combination of these two series will also satisfy the recursion. These linear combinations form a two-dimensional linear vector space; the original Fibonacci sequence can be found in this space.

Linear combinations of series varphi^{n} and (1-varphi)^{n}, with coefficients a and b, can be defined by

F_{a,b}(n) = avarphi^n+b(1-varphi)^n for any real a,b, .

All thus-defined series satisfy the Fibonacci recursion

Requiring that Fa,b(0) = 0 and Fa,b(1) = 1 yields a=1/sqrt 5 and b=-1/sqrt 5, resulting in the formula of Binet we started with. It has been shown that this formula satisfies the Fibonacci recursion. Furthermore, an explicit check can be made:

F_{a,b}(0)=

and

F_{a,b}(1)=

establishing the base cases of the induction, proving that

F(n)={{varphi^n-(1-varphi)^n} over {sqrt 5}} for all  n, .

Therefore, for any two starting values, a combination a,b can be found such that the function F_{a,b}(n), is the exact closed formula for the series.

[edit] Computation by rounding

Since for all ngeq 0, the number F(n) is the closest integer to varphi^n/sqrt 5, . Therefore it can be found by rounding, or in terms of the floor function:

F(n)=

[edit] Limit of consecutive quotients

Johannes Kepler observed that the ratio of consecutive Fibonacci numbers converges. He wrote that "as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost”, and concluded that the limit approaches the golden ratio varphi, .[10]

lim_{n

This convergence does not depend on the starting values chosen, excluding 0, 0. For example, the initial values 19 and 31 generate the sequence 19, 31, 50, 81, 131, 212, 343, 555 ... etc. The ratio of consecutive terms in this sequence shows the same convergence towards the golden ratio.

[edit] Proof

In brief, Fibonacci numbers are approximately exponential ��" F_{a,b}(n) approx kphi^n, where the constant depends on starting values ��" as the remaining term in the exact formula for the Fibonacci numbers becomes exponentially close to zero as n grows. Taking the ratio yields F(n+1)/F(n) approx (kphi^{n+1})/(kphi^n) = phi.

More formally, it must always follow from the explicit formula that for any real a 
e 0, , b 
e 0 ,

◄ GOING BACK-WARDS IN TIME: A Day In That Life

...and thus it goes. ►

Comments

Profile image

kealan coady

Fri 16th Oct 2009 00:36

this poem reminds me of acid

If you wish to post a comment you must login.

This site uses cookies. By continuing to browse, you are agreeing to our use of cookies.

Find out more Hide this message