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 x²g), 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) f_n = f_n-1+f_n-2

vi) f₀ =1 and f₁=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 f_n 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 f_n 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 f₀ and f₁) and any recursion (of the form f_n = Af_n-1+Bf_n-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 (x²+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?

OhMyEinstein says:

April 8, 2011 at 3:41 am

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?
Error: Unable to create directory uploads/2024/11. Is its parent directory writable by the server? The Physicist says:

April 8, 2011 at 11:49 am

-“Round to the nearest integer”
-By definition
-It’s just an example
Ron Ball says:

April 9, 2011 at 6:32 pm

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?
Pingback: Third Xamuel.com Linkfest
Johnny says:

June 6, 2011 at 6:16 pm

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.
Chris Hoare says:

July 6, 2011 at 8:44 am

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.
Error: Unable to create directory uploads/2024/11. Is its parent directory writable by the server? The Physicist says:

July 6, 2011 at 9:54 am

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.
Chris Hoare says:

July 7, 2011 at 4:55 am

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?
Error: Unable to create directory uploads/2024/11. Is its parent directory writable by the server? The Physicist says:

July 7, 2011 at 8:13 am

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.
Freya says:

April 27, 2013 at 7:51 pm

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?
Octopus says:

May 8, 2014 at 4:21 pm

A coincidence you say? I would think it is no more a coincidence than the fact 1 and 1 just happen to make 2. It is a natural law, is it not? The fibonacci sequence is very much related to the golden ratio as your formula shows.
Quentin says:

May 23, 2015 at 3:31 pm

I would like to observe that I do not believe we know enough to say that phi (the golden ratio) being in the expression for the nth Fibonacci number is a coincidence. Especially considering the limiting case, where F[n] represents the nth Fibonacci number, the ratio of F[n]/F[n-1] approaches phi as n approaches infinity.

That is only one place you notice Fibonacci numbers being related to the golden ratio. There are more, for example the definition of the golden ratio is that the ratio of the larger part to the smaller part be equal to the ratio of the sum of the larger part and smaller part, divided by the larger part. Put in mathematical terms that means:

x/a = (x+a)/x, where ‘x’ would be the “bigger part” and ‘a’ would be the smaller part. However, notice if you continue with this and take ‘x+a’ to be the larger part and x to be the smaller part. Now you get:

(x+a)/x = (2x+a)/(x+a) …………… continuing the process, what’s next is
(3x+2a)/(2x+a) and so on.

In general one can say that the golden ratio, or phi, is equal to:

(F[n+2]*x + F[n+1]*a)/(F[n+1]*x + F[n]*a) ————– n > 1, a > 0 where F[n] is the nth Fibonacci number.

So before anyone tells the fifteen year old not to wonder about the golden ratio and how it might relate to the Fibonacci sequence and what that means, we may want to reconsider.

A good scientist is not aware of what they know, but what they don’t know.

Also, our astute first poster neglected to observe that 1/2 – sqrt(5)/2 is actually 1/phi, or the inverse of the golden ratio… hmmmm.

I apologize for the lack of super/subscripts. Hope it is readable.
Manfred Muschiol says:

September 17, 2015 at 7:32 am

I supose, that the power 1+n should be n-1 in the formula. With that change, the nearest integer is according the Fibonacci sequence. e.g. n=10 is nearly 34 and n=11 Will be 55
Co says:

December 24, 2015 at 3:39 pm

as mathematicians we like to be very precise. When you say you are 15 it would be helpful to have a date to this. After a year you will be a year older. I have often thought the date info is created or broadcast is helpful. Sometimes full sense of information cant be made without a date
Elizabeth Leonard says:

November 28, 2016 at 5:54 pm

Is there a way to find the integral of the formula for the nth term of the fibonacci sequence?
Ya boiiiiiiiii says:

August 28, 2017 at 11:08 pm

I’m twelve and going like WHAAAAAAAAAAAAAAT?
Bruh
Make it easier
=D
bork says:

December 10, 2017 at 7:11 am

(n(n-1))/2
Anonymous says:

November 12, 2018 at 1:08 pm

dont put in the plus 1 to the power at the end and its much closer
Anonymous says:

November 12, 2018 at 1:26 pm

n not n+1 at the end of the formula
Sophie says:

May 13, 2019 at 2:03 am

This makes me feel stupid for even trying, I am only eleven and can barely find the nth term of a shape in a geometric pattern!! Why f1 etc!??
Anonymous says:

September 4, 2019 at 10:11 pm

Too technical for me.
My bad.
Beth says:

August 26, 2020 at 10:56 am

I don’t know what to do! urgh!🙁
my head is aching 😅

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

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

Leave a Reply Cancel reply

Send your questions about math, physics, or anything else you can think of to:

Subscribe via Email

Search the Archives

Categories

Archives

Recent