`F_n = (((1+sqrt(5))/2)^ "n" -((1-sqrt(5))/2)^ "n" )/sqrt5`

Enter a value for all fields

The n^th Fibonacci Number (Closed form) function returns n^th Fibonacci number using the closed form formula below.

INSTRUCTIONS: Enter the following:

• (n) Number of the Term

Fibonacci Number: The calculator returns the Fibonacci number as an integer.

The Math / Science

The Fibonacci Sequence is an integer sequence that starts with `0, 1` (or less commonly `1, 1`), with each following number found by adding the two previous:
     `0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...`
We can write this as the recurrence relation
     `F_n = F_(n-1) + F_(n-2)", with " F_0 =0" and " F_1=1`
However, this is inconvenient if we want to pick out, for example, the 25th Fibonacci number without having to go through and compute all the previous 24 to get to it. Luckily, because it is a linear recurrence with constant coefficients, we can find what is called a "closed form" for the Fibonacci numbers. That is, we can find a formula where all we have to do is plug in which term in the sequence we want to see, and it will give us the number. The closed form expression for the Fibonacci numbers is
     `F_n = ( ((1+sqrt5)/2)^n- ((1-sqrt5)/2)^n )/sqrt5`,

so if we wanted to find the 25th Fibonacci number we would do
     `F_25 = ( ((1+sqrt5)/2)^25- ((1-sqrt5)/2)^25 )/sqrt5 = 75025`.

(Note that with these indices we start counting from `0`, so `0` is the "`0`th" Fibonacci number, the `1`st is `1`, the `2`nd is `1`, the `3`rd is `2`, and so forth.)

Derivation of the Formula

Method 1: Using Linear Algebra

The construction of the Fibonacci sequence by adding the two previous terms can be achieved by multiplying the vector `(1, 0)^T` by the matrix
     `A=((1, 1), (1, 0))`

on the left:
     `((1, 1), (1, 0)) ((1), (0))=((1+0), (1+0))=((1),(1))`
     `((1, 1), (1, 0)) ((1), (1))=((1+1), (1+0))=((2),(1))`
     `((1, 1), (1, 0)) ((2), (1))=((2+1), (2+0))=((3),(2))`
     `((1, 1), (1, 0)) ((3), (2))=((3+2), (3+0))=((5),(3))`

And in general,
     `((1, 1), (1, 0)) ((F_n),(F_(n-1))) = ((F_n+F_(n-1)), (F_n)) = ((F_(n+1)), (F_n))`,
or
     `((1, 1), (1, 0))^n ((1),(0))=((F_(n+1)), (F_n))`

We will see that this matrix is diagonalizable (because it has distinct eigenvalues), which means that there exists some matrix `U` so that
     `U^-1 A U= ((lambda_1, 0), (0, lambda_2))`,
or
     `A=U((lambda_1, 0), (0, lambda_2)) U^-1`.

So if we want `A^n`, we can see that
     `A^n = U((lambda_1, 0), (0, lambda_2)) U^-1 U((lambda_1, 0), (0, lambda_2))U^-1 * * * U((lambda_1, 0), (0, lambda_2)) U^-1`
     `A^n=U((lambda_1, 0), (0, lambda_2))^n U^-1`
     `A^n=U((lambda_1^n, 0), (0, lambda_2^n)) U^-1`

So once we find this eigenvector matrix (`U`) and its inverse (`U^-1`), we will have
     `((F_(n+1)),(F_n))=A^n ((1),(0))=U((lambda_1^n, 0), (0, lambda_2^n))U^-1 ((1),(0))`.

First we need to find our eigenvalues. We take
     `det((1-lambda, 1),(1, -lambda))=(1-lambda)(-lambda)-1=0`

Then
     `lambda^2-lambda-1=0`,
and by the quadratic formula we get
     `lambda=(-(-1)+-sqrt((-1)^2-4(1)(-1)))/(2*1)`
     `lambda=(1+-sqrt(5))/2`.

Let `lambda_1=(1+sqrt(5))/2` and `lambda_2=(1-sqrt(5))/2`. Now we need to compute the eigenvalues. But before we do this, a few notes on these eigenvalues:

• `(1+sqrt(5))/2` is known as the Golden Ratio, often called `phi` (the Greek letter phi). `(1-sqrt(5))/2` is often labelled `Phi` (capital phi) or `psi` (the Greek letter psi). To avoid confusion, we'll refer to `(1-sqrt(5))/2` as  `psi`.
• The golden ratio is when the ratio between two quantities is equal to the ratio of their sum to the larger of the two quantities. That is, when `a>b` and `a/b=(a+b)/a=phi`.
• `psi=- 1/phi` (which is to say, `psi*phi=-1`), and is also equal to `-(phi-1)`.
• `phi+1=phi^2` and `psi+1=psi^2`

The last bullet point will be important in finding these eigenvectors. From now on we will refer to `lambda_1` as `phi` and `lambda_2` as `psi`, to avoid confusion. 

Starting with `phi`, we want to find the corresponding eigenvector. We have
     `((phi, 0), (0, phi))-((1, 1), (1, 0))=((0, 0), (0, 0))`
     `((phi-1, -1), (-1, phi)) "(subtract row 2 from row 1)"-> ((phi, -1-phi),(-1, phi))`
     `=((phi, -(phi+1)), (-1, phi)) = ((phi, -(phi^2)), (-1, phi)) "(divide row 1 by "phi")"`
     `->((1, -phi), (-1, phi)) "(add row 1 to row 2)" -> ((1, -phi), (0, 0))`

So `vec(v)_1=(phi, 1)^T`. An identical process, substituting `psi` for `phi` yields `vec(v)_2=(psi, 1)^T`. Now that we have `vec(v)_1` and `vec(v)_2`, we can construct `U`:
     `U=((phi, psi),(1, 1))`.

To find `U^-1`, recall that for a 2x2 matrix,
     `((a, b), (c, d))^-1 =1/(ad-bc) ((d, -b), (-c, a))`.
So
     `U^-1 = 1/(phi-psi) ((1, -psi),(-1, phi))`

Putting this all together, we get
     `((F_(n+1)), (F_n))= A^n ((1), (0)) = 1/(phi-psi) ((phi, psi),(1, 1)) ((phi^n, 0), (0, psi^n)) ((1, -psi),(-1, phi)) ((1), (0))`

     `((F_(n+1)), (F_n))=1/(phi-psi) ((phi^(n+1), psi^(n+1)), (phi^n, psi^n))((1, -psi),(-1, phi)) ((1), (0))`

     `((F_(n+1)), (F_n))=1/(phi-psi) ((phi^(n+1)-psi^(n+1), -psi phi^(n+1)+ phi psi^(n+1)),(phi^(n)-psi^(n), -psi phi^(n)+ phi psi^(n))) ((1), (0))`

     `((F_(n+1)), (F_n))=1/(phi-psi)((phi^(n+1)-psi^(n+1)), (phi^(n)-psi^(n)))`

Since `phi-psi=(1+sqrt(5))/2-(1-sqrt5)/2=(2sqrt5)/2=sqrt5`, we get

     `((F_(n+1)), (F_n))= ( ((phi^(n+1)-psi^(n+1))/(sqrt5)), ((phi^n-psi^n)/(sqrt5)) )`.

This shows us that
     `F_n = ( ((1+sqrt5)/2)^n-((1-sqrt5)/2)^n )/(sqrt5)`,
which was what we wanted.

Method 2: Using Generating Functions

Generating functions describe infinite sequences of numbers by setting the numbers as the coefficients of an infinite series. We call the sum of this series the "generating function" for the sequence, and it can be used in this case to find a closed form for our Fibonacci sequence.

First we need to write out what our series is.
     `F(x)=1+x+2x^2+3x^3+5x^4+8x^5+13x^6+ ...`
     `F(x)=sum_(n>=0) F_(n+1) x^n`

Here, `F(x)` is the generating function that we want to find. (Notice that we are really using the `n+1`th Fibonacci number; this won't make a difference in our result.)

Now we can use techniques similar to how we find the sum of a convergent geometric series to find our `F(x)`.
     `F(x)=1+x+2x^2+3x^3+5x^4+8x^5+13x^6+ ...`
  `xF(x)=        x+   x^2+2x^3+3x^4+5x^5+   8x^6+ ...`
`x^2F(x)=                  x^2+   x^3+2x^4+3x^5+  5x^6+ ...`

So
     `F(x)-xF(x)-x^2F(x)=1`
     `(1-x-x^2)F(x)=1`
     `F(x)=1/(1-x-x^2)`.

So we have our generating function, and
     `1/(1-x-x^2) = sum_(n>=0) F_(n+1) x^n`

Now if we can find a series expansion for this function we'll be able to find a closed form for the Fibonacci numbers. We want it to look something like
     `a/(1-bx)`,

which has the familiar power series expansion
     `sum_(n>=0) ab^n x^n`.

To get there, we first use partial fractions to write our generating function as the sum of two more manageable rational functions. So we need to factor the denominator. Using the quadratic formula again, we get
     `1-x-x^2=-(x+(1+sqrt5)/2)(x+(1-sqrt5)/2)`.

As in the first method, the golden ratio comes up. We'll again refer to `(1+sqrt5)/2` as `phi` and `(1-sqrt5)/2` as `psi`. So
     `1/(1-x-x^2)=-(1)/((x+phi)(x+psi))`,

and we want to find `A` and `B` so that
     `-(1)/((x+phi)(x+psi)) = A/(x+phi) +B/(x+psi)`

We have
     `-1=A(x+psi)+B(x+phi)`,
which we can solve easily by exploiting the fact that `x` is a variable. If we let `x=-phi`, the `B` term disappears and we have
     `-1=A(-phi+psi)`
     `-1=A(-sqrt5)`
     `A=1/sqrt5`.

Similarly, if we let `x=-psi`, the `A` term disappears and we have
     `-1=B(-psi+phi)`
     `-1=B(sqrt5)`
     `B=- 1/sqrt5`.

Plugging these in, we find that
     `1/(1-x-x^2)=-(1)/((x+phi)(x+psi))`

     `1/(1-x-x^2)=1/sqrt5 (1/(x+phi)-1/(x+psi))`.

This is closer to the form we want, but we want `a/(1-rx)`, so there's a bit more work to do. First let's just look at `1/(x+phi)`. If we multiply the numerator and denominator both by `psi` (which is the same as multiplying by `1`, so we're allowed) and recall the identities from above, we find
     `1/(x+phi)=1/(x+phi) * psi/psi`

     `1/(x+phi)=psi/(psi x-1)`

     `1/(x+phi)= - psi/(1-psi x)`.

We can do a similar trick with the other term and get
     `1/(x+psi)=1/(x+psi) * phi/phi`

     `1/(x+psi)= - phi/(1-phi x)`

Replacing those terms in the equation above with our new ones, we get
     `1/(1-x-x^2)=1/sqrt5 (- psi/(1-psi x) - (- phi/(1-phi x)))`

     `1/(1-x-x^2)=1/sqrt5 (phi/(1-phi x) - psi/(1-psi x))`.

Now everything is in a form we know how to work with, so we can write
     `1/sqrt5 (phi/(1-phi x) - psi/(1-psi x)) = 1/sqrt5( sum_(n>=0) (phi*phi^n x^n) + sum_(n>=0) (psi*psi^n x^n))`

     `1/sqrt5 (phi/(1-phi x) - psi/(1-psi x)) = sum_(n>=0) 1/sqrt5 (phi^(n+1)-psi^(n+1)) x^n`

Connecting all of this, we've found that
     `1+x+2x^2+3x^3+5x^4+8x^5+ ... = F(x)`

     `sum_(n>=0) F_(n+1) x^n = F(x)`
     `sum_(n>=0) F_(n+1) x^n = 1/(1-x-x^2)`
     `sum_(n>=0) F_(n+1) x^n = 1/sqrt5 (phi/(1-phi x) - psi/(1-psi x))`
     `sum_(n>=0) F_(n+1) x^n = sum_(n>=0) 1/sqrt5 (phi^(n+1)-psi^(n+1)) x^n`.

So `F_(n+1)` and `1/sqrt5 (phi^(n+1)-psi^(n+1))` are both the coefficients of the same series, so they must be equal. Since this is the `n+1`th Fibonacci number, if we want to find the `n`th we just need to change the index slightly and get
     `F_n = 1/sqrt5 (phi^(n)-psi^(n))`

     `F_n=( ((1+sqrt5)/2)^n- ((1-sqrt5)/2)^n )/sqrt5`
which was what we wanted.