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

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

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

  1. OhMyEinstein says:

    Ah a lot of maths!! too bad i’m still 15 and I’m not ready for this kind of math level : (
    Why “≈”?
    why fn = fn-1+fn-2?
    fn = Afn-1+Bfn-2? why : /
    Why Why Why Why?

  2. The Physicist The Physicist says:

    -”Round to the nearest integer”
    -By definition
    -It’s just an example

  3. Ron Ball says:

    Is there truly nothing? E.G., what does the universe exist in, or, stated another way, if the universe disappeared, what would you have left? Nothing? Something, (called nothing, which isn’t nothing if it’s something)? Does there exist a nothing which isn’t itself a subset of a larger nothingness?

  4. Pingback: Third Xamuel.com Linkfest

  5. Johnny says:

    Well, if nothing is something, then it is not nothing but something…

    Therefore in my opinion nothing must be nothing, and not something.

    So the subset of nothing is not something because nothing is not something…

    But to entertain the idea, that exist different kinds of nothingness, could be fun — like the idea that there are different cardinalities of infinity.

    And whether there truly exist (as in the physical reality) something that is nothing, I cannot imagine. Every time I imagine nothing, it can be black or empty space… I know it is not nothing but something, therefore I cannot imagine how nothing would exist.

    But then again, if nothing exist it is not nothing but something, and therefore I can conclude in my own mind that nothing does not truly exist.

    Nevertheless I think it is important, that mathematically nothing is defined, even though it may not exist in reality.

  6. Chris Hoare says:

    I may have missed this in the explanation, but the formula I learned is as follows:

    fib n = [((1+√5)/2)ⁿ- ((1-√5)/2)ⁿ]/√5

    I just tested it in a spreadsheet and it is correct.

    I hope it displays as intended. I created superscript and radical symbols in Linux.

  7. The Physicist The Physicist says:

    Your formula (starting at n=0) produces: 0,1,1,2,…
    The formula from the post (starting at n=0) produces: 1,1,2,3,…
    The only differences are in where they start, and the whole “rounding” thing.

  8. Chris Hoare says:

    I take your point completely. My answer was based on the original question, “Is there a formula to find the nth term in the Fibonacci sequence?” My bad.

    Rounding shouldn’t be an issue , should it?

  9. The Physicist The Physicist says:

    It ain’t!
    The second term in the formula is a number smaller than 1 raised to the Nth power which, (for powers of 2 and higher) is less than 0.5. Since the total formula always gives the correct answer, the first term is within 0.5 of the correct answer, and rounding just fixes the error.
    The only reason for ignoring the second term is to make the math easier to do by hand, and the behavior of the function easier to understand.

  10. Freya says:

    Hey, check this out! With this formula, if you are given a Fibonacci number F, you can determine its position in the sequence with this formula:

    n = log_((1+√5)/2)((F√5 + √(5F^2 ± 4)) / 2)

    Whether you use +4 or −4 is determined by whether the result is a perfect square, or more accurately whether the Fibonacci number has an even or odd position in the sequence. More accurately,

    n = log_((1+√5)/2)((F√5 + √(5F^2 + 4(−1)^n)) / 2)

    But that just won’t do, because we have n on both sides of the equation. We might be able to derive a general formula (from now on, (1 + √5) / 2 is represented by ϕ):

    ϕ^n = (F√5 + √(5F^2 + 4(−1)^n)) / 2
    2ϕ^n = F√5 + √(5F^2 + 4(−1)^n)
    2ϕ^n − F√5 = √(5F^2 + 4(−1)^n)
    4ϕ^n − 4F(√5)ϕ^n + 5F^2 = 5F^2 + 4(−1)^n
    4ϕ^n − 4F(√5)ϕ^n = 4(−1)^n
    ϕ^n − F(√5)ϕ^n = (−1)^n

    That’s as far as I can get. Would the mathematician please shed some light on how to isolate n?

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>