Q: Is there a formula to find the Nth term in the Fibonacci sequence?

Posted on April 8, 2011 by The Physicist

Physicist: Hells yes!  It’s f_n \approx \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}, where the “≈” is close enough that you can round to the nearest integer.  Astute readers will notice that \frac{1+\sqrt{5}}{2} is the golden ratio, and may wonder if this is a coincidence.  Yes.

Everything after this is a detailed, math-heavy explanation of where this formula comes from.

The “Fibonacci sequence” is defined as a sequence of numbers f_0, f_1, f_2, \cdots such that you have the recursion: f_n = f_{n-1}+f_{n-2}, and the restrictions: f_0 = 1 and f_1 = 1.

Explicitly, the Fibonacci sequence is: 1, 1, 2, 3, 5, 8, 13, 21, …  That is, the recursion says that every term is the sum of the previous two.

You can also talk about “generalized Fibonacci sequences”, where these restrictions and/or the recursion are changed.  For example: f_n = 2f_{n-1}+3f_{n-2}, with f_0 = 5 and f_1 = 2.  This derivation is for the ordinary sequence, but it can be altered to suit any generalized Fibonacci sequence.  Here it is:

Every now and again it’s useful to encode a string of numbers in a “generating function“.  For obscure (and unimportant to this post) reasons, you can write many functions as infinitely long polynomials.  For example: \sin{(x)} = x-\frac{1}{6}x^3+\frac{1}{120}x^5 \cdots.  The generating function for a sequence of numbers f_0, f_1, f_2, f_3, \cdots is g(x) = f_0 + f_1 x + f_2 x^2 + f_3 x^3 + \cdots = \sum_{n=0}^\infty f_n x^n.  So, sin(x) is the generating function for the sequence 0, 1, 0, -\frac{1}{6},0,\frac{1}{120}, \cdots.  If you can find a simple form for this function g, then bully.  You’ve got a very straight forward way of writing an infinite string of numbers.  The value of x doesn’t have anything to do with anything.  The powers of x are really just there to keep the numbers straight.  Now check this out!

\begin{array}{ll}g(x) = \sum_{n=0}^\infty f_n x^n\\xg(x) = \sum_{n=0}^\infty f_n x^{n+1} = \sum_{n=1}^\infty f_{n-1} x^n \\x^2 g(x) = \sum_{n=0}^\infty f_n x^{n+2} = \sum_{n=2}^\infty f_{n-2} x^n\end{array}

You can take the recursion and use it to find a relationship between these three slightly different functions.  Here’s a good first guess: g(x) = xg(x)+x^2g(x)

You can write this out, group by powers of x, and then use the recursion.  However (if you look at the definitions above for g, xg, and x2g), each sum starts at a different value of n.  That needs to be dealt with first:

\begin{array}{ll}i)&\sum_{n=0}^\infty f_nx^n=\sum_{n=1}^\infty f_{n-1}x^n+\sum_{n=2}^\infty f_{n-2}x^n\\ii)&\Rightarrow f_0+f_1x+\sum_{n=2}^\infty f_n x^n=f_0x+\sum_{n=2}^\infty f_{n-1}x^n+\sum_{n=2}^\infty f_{n-2}x^n\\iii)&\Rightarrow f_0+f_1x+\sum_{n=2}^\infty f_nx^n=f_0x+\sum_{n=2}^\infty (f_{n-1}+f_{n-2}) x^n\\iv)&\Rightarrow f_0+f_1x=f_0x+\sum_{n=2}^\infty (f_{n-1}+f_{n-2}-f_n)x^n\\v)&\Rightarrow f_0+f_1x=f_0x\\vi) &\Rightarrow 1+x =x\end{array}

ii) pulling out the n=0,1 terms

iii-iv) grouping by powers of x

v) fn = fn-1+fn-2

vi) f0 =1 and f1=1

This doesn’t quite line up, so the guess wasn’t perfect.  There should have been an extra “+1” on the right side of the original equation: g(x) = xg(x)+x^2g(x)+1

Armed with this latest equation we can actually solve for g:

\begin{array}{ll}g(x)=xg(x)+x^2g(x)+1\\\Rightarrow -1=xg(x)+x^2g(x)-g(x)\\\Rightarrow (x^2+x-1)g(x)=-1\\\Rightarrow g(x)=\frac{-1}{x^2+x-1}\\\Rightarrow g(x)=\frac{-1}{(x-R_+)(x-R_-)}\end{array}

Here R_+ = \frac{-1+\sqrt{5}}{2} and R_- = \frac{-1-\sqrt{5}}{2}.  The only reason for writing it this way is that leaving all those roots and fractions in makes this look like a math blizzard.

So far, using what is known about the Fibonacci sequence, we’ve found a nice closed equation for the generating function (g), which “encodes” the sequence.  Hopefully, we can use this fancy new equation to figure out what each fn must be.  Again, the function (g) itself does nothing.  The only reason it’s around is so that we can look at the coefficients when it’s written in the form of a (Taylor) polynomial.

Now using “partial fractions” you can pull this one kinda-complicated fraction into two not-so-complicated fractions (that’s where the “\frac{1}{\sqrt{5}}” comes from):

\begin{array}{ll} g(x)=\frac{-1}{(x-R_+)(x-R_-)}\\=\frac{1}{\sqrt{5}}\left[\frac{-1}{x-R_+}+\frac{1}{x-R_-} \right]\\=\frac{1}{\sqrt{5}}\left[\frac{1}{R_+-x}-\frac{1}{R_--x} \right]\\=\frac{1}{\sqrt{5}}\left[\frac{1}{R_+}\frac{1}{1-\frac{x}{R_+}}-\frac{1}{R_-}\frac{1}{1-\frac{x}{R_-}} \right]\end{array}

It so happens (and this is the point of the entire excercise) that functions of the form “\frac{1}{1-\square}” can be written as: \frac{1}{1-\square} = \sum_{n=0}^\infty \square^n = 1+\square+\square^2+\square^3+\cdots.  This is called a “geometric series“.  For example: 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots = \sum_{n=0}^\infty \left(\frac{1}{2}\right)^n = \frac{1}{1-\frac{1}{2}} = 2.

So, with that in mind:

\begin{array}{ll} g(x)=\frac{1}{\sqrt{5}}\left[\frac{1}{R_+}\frac{1}{1-\frac{x}{R_+}}-\frac{1}{R_-}\frac{1}{1-\frac{x}{R_-}} \right]\\=\frac{1}{\sqrt{5}}\left[\frac{1}{R_+}\sum_{n=0}^\infty \left(\frac{x}{R_+}\right)^n -\frac{1}{R_-}\sum_{n=0}^\infty \left(\frac{x}{R_-}\right)^n \right]\\=\frac{1}{\sqrt{5}}\left[\sum_{n=0}^\infty \left(\frac{1}{R_+}\right)^{n+1}x^n -\sum_{n=0}^\infty \left(\frac{1}{R_-}\right)^{n+1}x^n \right]\\=\sum_{n=0}^\infty \frac{1}{\sqrt{5}}\left(\frac{1}{R_+}\right)^{n+1}x^n -\sum_{n=0}^\infty \frac{1}{\sqrt{5}}\left(\frac{1}{R_-}\right)^{n+1}x^n\\=\sum_{n=0}^\infty \left[\frac{1}{\sqrt{5}}\left(\frac{1}{R_+}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1}{R_-}\right)^{n+1}\right]x^n\\\end{array}

But g was originally defined as g(x) = \sum_{n=0}^\infty f_n x^n.  These fn in front of each power of x must be the same as these weird things above.

\begin{array}{ll}f_n = \frac{1}{\sqrt{5}}\left(\frac{1}{R_+}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1}{R_-}\right)^{n+1}\\= \frac{1}{\sqrt{5}}\left(\frac{2}{-1+\sqrt{5}}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{2}{-1-\sqrt{5}}\right)^{n+1}\\= \frac{1}{\sqrt{5}}\left(\frac{2}{-1+\sqrt{5}}\frac{1+\sqrt{5}}{1+\sqrt{5}}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{-2}{1+\sqrt{5}}\frac{1-\sqrt{5}}{1-\sqrt{5}}\right)^{n+1}\\= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\end{array}

Notice: 1) \frac{1+\sqrt{5}}{2} = \phi is the golden ratio (not that it matters), and 2) \left|\frac{1-\sqrt{5}}{2}\right| \approx 0.6.  This means that the second term is smaller than one, and each successive power is progressively smaller.  So, rather than calculate it, ignore it!

Were you so inclined you could take any initial conditions (the f0 and f1) and any recursion (of the form fn = Afn-1+Bfn-2) and, using the method above, find a closed form for it as well.  The only problem you may run into is finding yourself with a polynomial that can’t be factored (x2+x-1 had factors, but it needn’t have).  If that happens, that’s bad…

Don’t know what to tell you.

This entry was posted in -- By the Physicist, Equations, Math. Bookmark the permalink.

22 Responses to Q: Is there a formula to find the Nth term in the Fibonacci sequence?

  1. Pingback: Third Xamuel.com Linkfest

Leave a Reply

Your email address will not be published. Required fields are marked *