A formula for Fib(n)

Contents of this Page

The Things To Do icon means there is a Things to do investigation at the end of the section. The calculator icon means there is an interactive calculator in this section.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. Calculator

Binet's Formula for the nth Fibonacci number

We have only defined the nth Fibonacci number in terms of the two before it:
the n-th Fibonacci number is the sum of the (n-1)th and the (n-2)th.
So to calculate the 100th Fibonacci number, for instance, we need to compute all the 99 values before it first - quite a task, even with a calculator!
A natural question to ask therefore is:
Can we find a formula for F(n) which involves
only n and does not need any other (earlier) Fibonacci values
?
Yes! It involves our golden section number Phi and its reciprocal phi:
Here it is:
Fib(n) = Phin – (–Phi)–n  =  Phin – (–phi)n

sqrt5

sqrt5

where Phi = 1·61803 39887 49894 84820 45868 34365 63811 77203 09179 80576 ... .
The next version uses just one of the golden section values: Phi, and all the powers are positive:
Fib(n) = 
Phin (–1)n

Phin

sqrt5

Since phi is the name we use for 1/Phi on these pages, then we can remove the fraction in the numerator here and make it simpler, giving the second form of the formula at the start of this section.

We can also write this in terms of sqrt5 since Phi = 1 + sqrt5  and –phi = 1 – sqrt5  :

2

2

Fib(n) =  Phin – (–phi)n = Phin–(–phi)n = 1((1 + √5)n(1 – √5)n)
----------
Phi – (–phi)√5√522

If you prefer values in your formulae, then here is another form:-

Fib(n) =  1.6180339..n – (–0.6180339..)n

2.236067977..

This is a surprising formula since it involves square roots and powers of Phi (an irrational number) but it always gives an integer for all (integer) values of n!

Here's how it works: Phi =(1·618..) and -phi=-0·618..: Try some other values of n here, but remember that this calculator has some built-in limits for the number of decimal places it can accurately compute. Sometimes these inaccuracies will make numbers round to the wrong values.
You should be suspicious of large numbers that end with 0 because this could indicate a loss of some of the final digits. Only the left-hand digits of a large number are correct -- the question is just how many!

But the mathematics does tell us that the resulting Fib(n) really should be an integer for all values of n! We will return to this problem in the next section.

C A L C U L A T O R
Fib(n) using Binet's Formula with n=
R E S U L T S:
You might want to look at two ways to prove this formula: the first way is very simple and the second is more advanced and is for those who are already familiar with matrices.

An approximation is good enough

Since phi is less than one in size, its powers decrease rapidly. We can use this to derive the following simpler formula for the n-th Fibonacci number F(n):

F(n) = round( Phin / √5 ) provided n ≥ 0
where the round function gives the nearest integer to its argument. Notice how, as n gets larger, the value of Phin/√5 is almost an integer.
If n<0 then the powers of (-phi) become larger than the same power of Phi, so then we use
F(n) = round( (-phi)n / √5 ) provided n < 0
C A L C U L A T O R
rounded powers of Phi and (-phi) when n=
R E S U L T S:

/ Things to do /

  1. What is F(100) according to Binet's formula?
    The first calculator will give you some of the initial digits, but the right-hand digits will be wrong. You may choose to write a computer program for this, or use a package (such as Mathematica or Maple) which lets you work out very long integers exactly.
  2. How many digits does F(100) have? (the approximate value on the first calculator above should tell you). Check your answer with the list of Fibonacci numbers.
  3. Look at the following table:
    n: Phin=X: (-Phi)-n=Y: X-Y: (X-Y)/sqrt(5):
    11·618033989 -0·61803399 2·23606798 1
    You might nave noticed that we didn't ADD the X and Y values to get 1·618..-0·618..=1 directly but instead in Binet's Formula, we subtracted and divided by sqrt(5).
    Let's see what happens if we do just ADD the X and Y columns:
    (a) Add a new column to the table above which is X+Y. Fill it in and you'll notice something very surprising - another integer series that is not the Fibonacci numbers!! These numbers are called the Lucas Numbers and they also have some similar properties to the Fibonacci numbers and are covered in another page at this site (see Fibonacci Home page).
    (b) Can you spot the rule whereby the latest two Lucas numbers are used to generate the next Lucas number?

Historical Note - Binet's, de Moivre's or Euler's Formula?

Many authors say that this formula was discovered by J. P. M. Binet (1786-1856) in 1843 and so call it Binet's Formula.
Graham, Knuth and Patashnik in Concrete Mathematics (2nd edition, 1994) mention that Euler had already published this formula in 1765.
But Don Knuth in The Art of Computer Programming, Volume 1 Fundamental Algorithms, section 1.2.8, traces it back even further, to A de Moivre (1667-1754). He had written about "Binet's" formula in 1730 and had indeed found a method for finding formulae for any general series of numbers formed in a similar way to the Fibonacci series.
Like many results in Mathematics, it is often not the original discoverer who gets the glory of having their name attached to the result, but someone later!

Book: Concrete Mathematics (2nd edition, 1994) by Graham, Knuth and Patashnik, Addison-Wesley.
Book: The Art of Computer Programming D E Knuth, Volume 1: Fundamental Algorithms (now in its Third Edition, 1997).

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. Calculator

How many digits does a number have?

Using the display on your calculator

One of the questions above asks you to use your calculator to find out how many digits are in a number. When the number gets too big for the calculator's display, it shows the first few digits and a little "exponent" which says how to move the decimal place from where it is shown to it true place - negative means move it to the left, otherwise move it to the right from where it is shown in the display.
So Phi20/sqrt(5) on my calculator is 6765·000029 and Fib(20)=6765.
But Phi60/sqrt(5) shows as 1·548008755 12 where the little figures at end are the "exponent", that is, the true value is 1·548008755x1012. If we move the decimal point 12 places to the right (putting in 0s for the missing digits), we get:
1548008755000. and the correct value for Fib(60) is
1548008755920
So the exponent, when positive, has told us how many digits there are in the number calculated, showing just the first few of the digits if not all of them will fit into the display window!

Similarly, phi60 is just 1/Phi60 which we've just calculated. Using the "1/x" button on my calculator when it is showing the value above gives: 6·459911784-13 meaning 6·459911784x10-13. This time we must move the decimal place to the left since the exponent is negative and we must move it 13 places. This gives 0·00000000000064511784 as the value for phi60 - quite small!

Using the LOG button on your calculator

But how can we calculate the number of digits in a given whole number?
This section shows how to use the LOG button on your calculator to find out how long a number is.

Returning to the investigation above where you calculated F(100), this number is usually too big for most calculators to compute, but we can find how long it is as follows, using the simplified formula:

Fib(n) = round( Phin/√5 )
[This very nearly gives the correct value of F(n) since the part of the formula we have omitted is very small indeed for large n.]
The LOG button on your calculator can be used to compute how long a number is, that is, how many decimal digits it has.

How many digits are there in Fib(n)?

So, now you have enough information to answer the question:
How many digits has F(1000)?
Computing LOG (Phi1000/√5) is the same as computing
1000*LOG(Phi) - (LOG √5) = 1000*LOG Phi - (LOG 5)/2 = 208.638155.
So 1+the whole number part of your answer is the number of digits in F(1000), i.e. 209 digits.
In fact, you can find the first few digits by using the rest of the LOG answer as we'll see in the next section.

What are the first few digits of Fib(n)?

The whole number part of the log tells us how many digits are in the number. The rest of the log of a number tells us what those initial digits are. This is because if the log of the number is xxxx.yyyyyy then the number itself is 10xxxx.yyyyyy=10xxxx+0.yyyyyy=10xxxx x 100.yyyyyy
10xxxx is just a power of ten so it tells us how to move the decimal point in 100.yyyyyy.
Since 0.yyyy is between 0 and 1 and 100=1 and 101=10 then
100.yyyyyy has a single non-zero digit before its decimal point.

The part after the decimal point in number r is often called the fractional part of r and written as frac(r).
So the first few digits of a number r are given by 10frac(log10(r)).
C A L C U L A T O R
up to
R E S U L T S
There is a PUMAS (Practical Uses of Maths and Science) page by Kim Aaron, of the Jet Propulsion Lab, entitled "Just what is a log anyway?" It shows how Kim has found many practical uses of logarithms as a working engineer.
This page is designed for middle school students, but teachers will also find it well worth checking out too!

Finding Fibonacci Numbers Fully

If we want to study the full and exact integer form of a Fibonacci number, how do we do it? We will assume that our calculator or computer can add, subtract and multiply whole numbers of any length (such as Maple or Mathematica). [If not, it is an interseting and easy programming exercise to represent integers of any length as an array of single digits together with functions that manipluate them to perform addition, subtraction and multiplication using the rules that we all learned at school.] We have the basic recursive definition, of course (where recursive just means that we are defining one value of F in terms of two other, simpler, values of F):
F(0)=0
F(1)=1
F(n) = F(n-1) + F(n-2), n>1
but the disadvantage is that to calculate F(1000), for example, we need to compute all 999 numbers before it.
Alternatively, using Binet's formula above means we need to compute many decimal places of √5.
So the question we have is:
Can we find a quicker method using only integers?
One method was proposed by the late Prof. Edsgar W Dijkstra around 1978, described in note EWD654 "In honor of Fibonacci" (PDF, 38K; download the free Acrobat Reader to view it if your browser will not display it).
Note that Dijkstra's series begins F(1)=0 and F(2)=1 so, using our index system which has F(0)=0 and F(1)=1, we have:
F(2n-1) = F(n-1)2 + F(n)2
F(2n) = ( 2 F(n-1) + F(n) ) F(n)
which need only F(n) and F(n-1) to compute both F(2n) and F(2n-1). Although the formula in Dijkstra's note were "well-known" in 1978, his method of using these two formula in this way as an efficient algorithm for computing big Fibonacci numbers may be original.
So, to compute F(1000) we would use the two formulae as follows: So there are very few (22) F values needed to compute F(1000) and it takes much less work than using the method of "add the previous two F values to get the next one".

See also Computers use the Rabbit Sequence on the Golden String page at this site for another insight into computers and computing Fibonacci numbers.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. Calculator

Calculating the next Fibonacci number directly

Suppose we have evaluated Fib(100) and we want to know the next value: Fib(101). Do we have to use Binet's formula again? Well we could do, of course, but here is a short-cut.

There is also a formula that, given one Fibonacci number, returns the next Fibonacci number directly, calculating it in terms only of the previous value (ie not needing the value before as well).

F(n+1) = round( F(n) Phi )
The round function applies to a number (whole or decimal) and changes it to an integer.

An example

Here's an example of our "next Fibonacci" formula using a small value of n:
Since F(4)=3 then
F(5)
= round( 3 Phi )
= round( 3x1·618... )
= round( 4·854... )
= 5 which is correct!

But there's a problem....

F(1)=1 and the next Fibonacci number is F(2)=1.
ALSO, F(2)=1 but the next Fibonacci number is F(3)=2.
But we cannot have two different values for "the next Fibonacci number after 1"!
If we put F(n)=1 in the formula, we have round(1 x Phi), or the nearest integer to Phi = 1.618..., which is 2.
So we cannot apply this formula when n is 1 (and you can check that it also fails if n is 0).
So we have an important restriction on the formula above: the formula only applies when n is bigger than 1.

F(n+1) = round( F(n) Phi )    for all n > 1

Proving that this formula is correct

You can easily evaluate F(2) from F(1)=1 and F(3) from F(2)=2 by this formula and see that they give F(2)=3 and F(3)=5. Then, if you are familiar with proof by induction you can show that, supposing the formula is true for F(n-1) and F(n) then it must also be true for F(n+1) by showing that adding the formula's expressions for F(n) and F(n-1) gives the formula's expression for F(n+1).

Other ways of proving it involve results about recurrence relations and how to solve them, which are very like solving differential equations, except that they deal with integer values not real number values. This is often included in university level courses on Pure or Discrete Mathematics.

[ For the university level mathematician, there is an interesting HAKMEM note on a fast way of computing Fibonacci numbers and its applications.]

Detecting when N is a Fibonacci Number

Given a number N it is not easy to spot if it is a Fibonacci number or not.
Is there a simple test to see if N is a Fibonacci number?
I Gessel solved this in 1972 with a surprisingly simple test.
N is a Fibonacci number if and only if 5 N2 + 4 or 5 N2 – 4 is a square number.
For instance, It is easy to test if a whole number is square on a calculator by taking its square root and checking that it has nothing after the decimal point.
In a computer programming language, take the square root, round it to the nearest integer and then square the result. If this is the same as the original whole number then the original was a perfect square.

To detect which Fibonacci number it is, that is, to find the index number i for which n = Fib(i), we can use the approximate version of Binet's formula from above:

Fib(i) = round( Phii/√5 )
If n is Fib(i), then n√5 is approximately Phii
Taking LOGS (to base 10) of both sides gives:
LOG(n √5) = LOG( Phii) and using the log rules we have:
LOG(n) + LOG(5)/2 = i LOG(Phi) so that
i = (LOG(n) + LOG(5)/2)/LOG(PHI)
Since our formula was approximate, then rounding this value to the nearest integer should be sufficient to give the real (whole number) index i for which Fib(i)=n.
C A L C U L A T O R
Is a Fibonacci number
R E S U L T S
Article: Problem H-187: n is a Fibonacci number if and only if 5n2+4 or 5n2-4 is a square posed and solved by I Gessel in Fibonacci Quarterly (1972) vol 10, page 417.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. Calculator

Binet's Formula for negative n?

Earlier on this page we looked at Binet's formula for the Fibonacci numbers:
Fib(n) = { Phi n - (-phi) n } / √5
Here Phi=1·6180339... and phi = 1/Phi = Phi-1 = (√5-1)/2 = 0·6180339... .

We only used this formula for positive whole values of n and found - surprisingly - it only gives integer results. Well perhaps it was not so surprising really since the formula is supposed to be define the Fibonacci numbers which are integers; but it is surprising in that this formula involves the square root of 5, Phi and phi which are all irrational numbers i.e. cannot be expressed exactly as the ratio of two whole numbers.

Suppose we try negative whole numbers for n in Binet's formula.
The formula extends the definition of the Fibonacci numbers F(n) to negative n.
In fact, if we try to extend the Fibonacci series backwards, still keeping to the rule that a Fibonacci number is the sum of the two numbers on its LEFT, we get the following:

n :...-6-5-4-3-2-10123456...
Fib(n):...-85-32-110112358...
and this is consistent with Binet's formula for negative whole values of n.
So we can think of Fib(n) being defined an all integer values of n, both positive and negative and the Fibonacci series extending infinitely far in both the positive and negative directions.

Binet's formula for non-integer values of n?

This section is optional and at an advanced level i.e. post 16 years education.
Take me back to the Fibonacci Home page now
or learn about square roots of negative numbers in what follows!

Well now we've tried negative values for n, why not try fractional or other non-whole values for n?
This doesn't make sense in terms of numbers in a series (there is a 2nd and a 3rd term and even perhaps a -2nd term but what can we possibly mean by a 2·5th term for instance)??
However, this could give us some interesting (mathematical) insights into the whole-number terms which are our familiar Fibonacci series.

Complex Numbers

The trouble is that in Binet's formula:

Fib(n) = { Phi n - (-phi) n }/√5
the second term (-phi)n means we have to find the n-th power of a negative number: -phi and n is not a whole number. If n was 0·5 for instance, meaning sqrt(-phi), then we are taking the square-root of a negative value which is "impossible".

Mathematicians have already extended the real-number system to cover such "imaginary" numbers. They are called complex numbers and have two parts A and B, both normal real numbers: a real part, A, and an imaginary part, B. The imaginary part is a multiple of the basic "imaginary" quantity √-1, denoted i. So complex numbers are written as x + i y or x + y i or sometimes as x + I y or even more simply as (x,y).

Applications of Complex numbers

To me it is still surprising that such "imaginary" numbers - or numbers involving the imaginary quantity that is the square root of a negative number - have very practical applications in the real world.
For instance, electrical engineers have already found many applications for such "imaginary" or complex numbers. Whereas resistance can be described by a real number often measured in ohms, complex numbers are used for the inductance and capacitance, so they have very practical uses!
Electrical engineers tend to use j rather than i when writing complex numbers.

Mathematicians find uses for complex numbers in solving equations:

This leads to a beautiful theorem about solving equations which are sums of (real number multiples of) powers of x, called polynomials in x:
If the highest power of x in a polynomial is n then there are at most n complex number solutions which make the polynomial's value zero

Book: Complex Numbers and Their Applications by F J Budden, Longman's 1968, is now out of print but is an excellent introduction to the fascinating subject of complex numbers and their applications.

Argand Diagrams

Writing (x,y) for a complex numbers suggests we might be able to plot complex numbers on a graph, the x distance being the real part of a complex number and the y height being its complex part.

Such plots are called Argand diagrams after J. R. Argand (1768-1822).
Argand diagram We can plot an individual point such as 1 - 2i as the point (1,-2). Numbers which are real have zero as their complex part so the real number 3 is the same as the complex number 3 + 0 i and has "coordinates" (3,0). The real number -1·5 is the same as -1·5 + 0 i or (-1·5,0).
In general, the real number r is the complex number r + 0 i and is plotted at (r,0) on the Argand diagram.
In fact, all the real values are already in the graph along the x axis also called the real axis.
Numbers which are purely imaginary have a real-part of zero and so are of the form 0+yi always lying exactly on the y axis ( the imaginary axis).

Plotting functions on an Argand Diagram

We can plot a complex function on an Argand diagram, that is, a function whose values are complex numbers. This is where Binet's formula comes in since it will give us complex numbers as n varies over the real numbers.

So what happens if we plot a graph of F(n) described by Binet's formula, plotting the results on an Argand diagram?

The blue plot is for positive values of n from 0 to 6. Note how this curve crosses the x axis (representing the "real part of the complex number") at the Fibonacci numbers, 0, 1, 2, 3, 5 and 8. But there is a loop so it crosses the axis twice at x=1, and we really do get the whole Fibonacci sequence 0,1,1,2,3,5,8.. as the crossing points.
The red plot is of negative values of n from -6 to 0. It also crosses the x axis at the values -8, 5, -3, 2, -1, 1 and 0 corresponding to the Fibonacci numbers F(-6), F(-5), F(-4), F(-3), F(-2), F(-1) and F(0).
fib neg fib pos
Spirals?

The plots were produced using parametric plotting function with Maple's built-in "plot" function:
      Phi:=(sqrt(5)+1)/2;phi:=(sqrt(5)-1)/2;
      f:=n->(Phi^n-(-phi)^n)/sqrt(5);
      plot([Re(f(n)),Im(f(n)),n=-6..0],color=RED,
           title=`Fib(n),-6≤n≤0, Argand diagram`);
      plot([Re(f(n)),Im(f(n)),n=0..6],color=BLUE,
           title=`Fib(n),0≤n≤6, Argand diagram`);
Kurt Papke has a Web page with a Java applet to show the two Argand diagrams but animating the formula that f(n)=f(n-1)+f(n-2) for any real value n. The complex numbers f(n), f(n-1) and f(n-2) can be illustrated as vectors, and so the formula f(n)=f(n-1)+f(n-2) becomes a vector equation showing that the vector f(n-1) added to (followed by) the vector f(n-2) gives the same length-and-direction-movement as the vector f(n).
Kurt has an excellent 3D version of the spiral that you can rotate on the screen (using a Java applet) AND one also for the Lucas numbers formula!

For a different complex function based on Binet's formula, see the following two articles where they both introduce the factor ei n pi which is 1 when n is an integer:
Article: Argand Diagrams of Extended Fibonacci and Lucas Numbers, F J Wunderlich, D E Shaw, M J Hones Fibonacci Quarterly, vol 12 (1974), pages 233 - 234;
Article: An Extension of Fibonacci's Sequence P J deBruijn, Fibonacci Quarterly vol 12 (1974) page 251 - 258;

References on Complex Numbers

Complex Numbers are included in some (UK based) Mathematics syllabuses at Advanced level (school/college examinations taken at about age 17). Here are some books relating to different Advanced level Examination Boards syllabus entries on Complex Numbers:
Book: GCE A level Maths: Complex Numbers A. Nicolaides,ISBN: 1872684270, 1995.
Book: Nuffield Advanced Mathematics: Complex Numbers and Numerical Analysis June 1994, Longman, ISBN: 0582099846.
Book: School Maths Project 16-19: Complex Numbers Cambridge, 1992, ISBN: 0521426529.

Valid HTML 4.01! © 1996-2009 Dr Ron Knott email
updated 6 August 2009