# I need a simple formula for calculating Fibonacci numbers...

**URL:** <https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330>\
**Category:** Factual Questions\
**Created:** [December 30, 2004, 11:01pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330 "2004-12-30T23:01:57Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![Captain\_Carrot](https://avatars.discourse-cdn.com/v4/letter/c/f0a364/32.png) [@Captain\_Carrot](https://boards.straightdope.com/u/Captain_Carrot)\
**Post date:** [December 30, 2004, 11:01pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/1 "2004-12-30T23:01:57Z")

</div>

I have discovered an equation that generates powers of phi, the golden ratio ((5^.5+1)/2), but it relies on Fibonacci numbers for its output:  
If x\>=1, phi^x=F(x)_phi+F(x-1)  
If x\<=-1, phi^x=(-1)^x_F(x)\*phi+(-1)^(x+1)\*F(x-1)  
phi^0=1  
where F(x)=Fibonacci number x.

Since this equation calculates powers of phi, I can’t use an equation for Fib. numbers that uses powers of phi. Can anyone help me out here? (Do not inform me that F(x)=F(x-1)+F(x-2). I know that.)

Thanks for your help!

---

<div class="post-metadata">

**Author:** ![OldGuy](https://avatars.discourse-cdn.com/v4/letter/o/3bc359/32.png) [@OldGuy](https://boards.straightdope.com/u/OldGuy)\
**Post date:** [December 30, 2004, 11:31pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/2 "2004-12-30T23:31:27Z")

</div>

Rather than tell you the answer, let me show you how to solve this problem. We know f(x+2)=f(x+1)+f(x), and also that f(0)=f(1)=1.

This is a linear equation with constant coefficients so we guess a solution f(x) = Aa^x. Substituting this into the equation gives

```
  Aa^(x+2) = Aa^(x+1) + Aa^x or a^2 = a + 1 or a^2 - a - 1 = 0

```

The last is a quadractic equation in a = [1 {+ or -} sqrt(5)]/2. That is a is equal to the golden ratio phi = 1.618034… or 1 - phi = -0…618034. So now we have the general solution as a linear combination of these two solutions for any constant A (called A and B for the two solutions)

```
 f(x) = A*phi^x + B*(1-phi)^x

```

A and B can be determined by the two values we know.

```
1 = f(0) = A + B
1 = f(1) = A*phi + B*(1-phi).

```

Solving these two equations gives A = phi/(2_phi - 1) B = (phi - 1)/(2_phi - 1). So our final answer is

f(x) = [phi^(x+1) - (1-phi)^(x+1)]/(2\*phi -1)

---

<div class="post-metadata">

**Author:** ![Captain\_Carrot](https://avatars.discourse-cdn.com/v4/letter/c/f0a364/32.png) [@Captain\_Carrot](https://boards.straightdope.com/u/Captain_Carrot)\
**Post date:** [December 30, 2004, 11:56pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/3 "2004-12-30T23:56:30Z")

</div>

Yes, thank you, **Oldguy** , but since my equation is designed to compute phi^x, I can’t use an equation for Fibonacci numbers that needs phi^x. (Which, oddly enough, I think I mentioned in my OP.)

Dang it, why do I sound so cold and mean online? I really don’t mean to do that.

---

<div class="post-metadata">

**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\
**Post date:** [December 31, 2004, 12:19am UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/4 "2004-12-31T00:19:41Z")

</div>

> [@dwalin](#):
>
> I have discovered an equation that generates powers of phi, the golden ratio ((5^.5+1)/2), but it relies on Fibonacci numbers for its output:  
> If x\>=1, phi^x=F(x)_phi+F(x-1)  
> If x\<=-1, phi^x=(-1)^x_F(x)\*phi+(-1)^(x+1)\*F(x-1)  
> phi^0=1  
> where F(x)=Fibonacci number x.
> 
> Since this equation calculates powers of phi, I can’t use an equation for Fib. numbers that uses powers of phi. Can anyone help me out here? (Do not inform me that F(x)=F(x-1)+F(x-2). I know that.)
> 
> Thanks for your help!

I hate to tell you, but the easy way to generate F[sub]n[/sub] is basically an inversion of your “discovered” equation. Want a closed form for F[sub]n[/sub]? It uses powers of phi.

---

<div class="post-metadata">

**Author:** ![jmizzou](https://avatars.discourse-cdn.com/v4/letter/j/edb3f5/32.png) [@jmizzou](https://boards.straightdope.com/u/jmizzou)\
**Post date:** [December 31, 2004, 12:20am UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/5 "2004-12-31T00:20:10Z")

</div>

Try [Binet’s Formula](http://www.geocities.com/cyd_conner/binetsFormula.gif), where _x_ is the _x_th Fibonnaci number.

---

<div class="post-metadata">

**Author:** ![TJdude825](https://avatars.discourse-cdn.com/v4/letter/t/dec6dc/32.png) [@TJdude825](https://boards.straightdope.com/u/TJdude825)\
**Post date:** [December 31, 2004, 3:29am UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/6 "2004-12-31T03:29:02Z")

</div>

I think you mean F(x) is the xth Fibonacci number. Note that the (1+sqrt5)/2 in the formula is phi.

---

<div class="post-metadata">

**Author:** ![jmizzou](https://avatars.discourse-cdn.com/v4/letter/j/edb3f5/32.png) [@jmizzou](https://boards.straightdope.com/u/jmizzou)\
**Post date:** [December 31, 2004, 4:24am UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/7 "2004-12-31T04:24:45Z")

</div>

> [@TJdude825](#):
>
> I think you mean F(x) is the xth Fibonacci number.

Maybe I should have phrased that better. _x_ is the _x_th place of the Fibonacci sequence. _f(x)_ is, indeed, the _x_th value in the Fibonacci sequence.

> [@TJdude825](#):
>
> I think you mean F(x) is the xth Fibonacci number. Note that the (1+sqrt5)/2 in the formula is phi.

I must be slipping in my old age. I think I’ll just take **Mathochist** at his/her word.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [December 31, 2004, 6:41am UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/8 "2004-12-31T06:41:02Z")

</div>

The easiest way to calculate Fibonacci numbers by hand is through a method known as dynamic programming. Without getting into all the details, you keep a three place array with the first three Fibonacci numbers, and then calculate the next one by adding the previous two, mod 3. Does that make sense?

---

<div class="post-metadata">

**Author:** ![David\_Simmons](https://avatars.discourse-cdn.com/v4/letter/d/9de053/32.png) [@David\_Simmons](https://boards.straightdope.com/u/David_Simmons)\
**Post date:** [December 31, 2004, 2:51pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/9 "2004-12-31T14:51:33Z")

</div>

I’m curious. Was it or was it not decided that there is (or is not) a simple, closed form method?

I’ve thought that you have to use a subroutine, start from the beginning and go up to n each time you need to compute one of them…

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [December 31, 2004, 5:28pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/10 "2004-12-31T17:28:10Z")

</div>

It is _far_ faster to compute Fibonacci numbers using repeated squaring. Either thru Binet’s formula or methods such as repeated squaring of the [Fibonacci Q-Matrix](http://mathworld.wolfram.com/FibonacciQ-Matrix.html). Ergo only a logarithmic number of operations are required rather than linear.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [December 31, 2004, 8:03pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/11 "2004-12-31T20:03:17Z")

</div>

> [@David Simmons](#):
>
> I’m curious. Was it or was it not decided that there is (or is not) a simple, closed form method?
> 
> I’ve thought that you have to use a subroutine, start from the beginning and go up to n each time you need to compute one of them…

Yes, but that’s _very_ quick, and easy to program.

---

<div class="post-metadata">

**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\
**Post date:** [January 2, 2005, 5:18pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/12 "2005-01-02T17:18:50Z")

</div>

> [@David Simmons](#):
>
> I’m curious. Was it or was it not decided that there is (or is not) a simple, closed form method?
> 
> I’ve thought that you have to use a subroutine, start from the beginning and go up to n each time you need to compute one of them…

There _is_ a simple closed-form method for calculationg the Fibonacci sequence, but it _uses powers of phi_ (which the OP wants to use Fibonacci to calculate). In fact, I already mentioned this in my response to the OP. Did I accidentally use the “invisible” tag?

---

<div class="post-metadata">

**Author:** ![David\_Simmons](https://avatars.discourse-cdn.com/v4/letter/d/9de053/32.png) [@David\_Simmons](https://boards.straightdope.com/u/David_Simmons)\
**Post date:** [January 2, 2005, 5:31pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/13 "2005-01-02T17:31:57Z")

</div>

> [@Mathochist](#):
>
> There _is_ a simple closed-form method for calculationg the Fibonacci sequence, but it _uses powers of phi_ (which the OP wants to use Fibonacci to calculate). In fact, I already mentioned this in my response to the OP. Did I accidentally use the “invisible” tag?

This is an exposition of a simple closed-form method?

“I hate to tell you, but the easy way to generate Fn is basically an inversion of your “discovered” equation. Want a closed form for Fn? It uses powers of phi.”  
“Did I accidentally use the “invisible” tag?”

Might as well have.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [January 2, 2005, 6:03pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/14 "2005-01-02T18:03:10Z")

</div>

OK, I’ve been on a laptop all of last week, so my ability to post has been limited. Let’s briefly discuss various methods of calculating Fibonacci numbers.

As **Mathochist** alluded to, there is a closed form formula for calculating F[sub]n[/sub], but it relies on knowing the value of [symbol]f[/symbol], so that won’t do you any good. Since [symbol]f[/symbol] is an irrational number, you also may have to worry about floating point accuracy (but not unless you’re dealing with large values of n).

**ftg** ’s methods are undoubtedly the fastest you’ll find easily, but I don’t think you’d consider them to be simple, especially if you’re doing this by hand. If you’re programming, it really depends on what environment you’re programming in–in C++, that’s the way to go, but on a TI-83, it’s not.

The dynamic programming method I outlined above is simple enough to be executed by hand and reasonably fast for small to medium values of n.

The traditional recursive method is actually one of the worst published algorithms I’ve seen. It fails because you end up computing each F[sub]k[/sub] (k \< n) multiple times, and that gets expensive.

Of course, let’s not forget a very important fact here–the Fibonacci numbers don’t change between runs of your program. Stick them in a file, and do a lookup to see if you already know the value. If you do, return that; if not, compute that value and all the intermediate ones you don’t have, and stick those in the file.

---

<div class="post-metadata">

**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\
**Post date:** [January 2, 2005, 6:05pm UTC](https://boards.straightdope.com/t/i-need-a-simple-formula-for-calculating-fibonacci-numbers/282330/15 "2005-01-02T18:05:14Z")

</div>

> [@David Simmons](#):
>
> This is an exposition of a simple closed-form method?
> 
> “I hate to tell you, but the easy way to generate Fn is basically an inversion of your “discovered” equation. Want a closed form for Fn? It uses powers of phi.”  
> “Did I accidentally use the “invisible” tag?”
> 
> Might as well have.

Ah, but you asked if there _exists_ such, not what it is.

F[sub]n[/sub] = (phi[sup]n[/sup] - (-phi)[sup]-n[/sup]) / sqrt(5)