# Talk:Fibonacci number

WikiProject Mathematics (Rated B-class, High-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 B Class
 High Importance
Field:  Number theory
One of the 500 most frequently viewed mathematics articles.

## Jaime and Cersei

Someone has replaced the rabbits with Jaime and Cersei from Game of Thrones.

Okay, someone fixed this already. — Preceding unsigned comment added by 161.53.138.248 (talk) 10:58, 26 February 2015‎ (UTC)

## Extracting closed-forms from generating function's power series

Another approach to computing Fn, suggested by Paul Hankin, is to extract Fn from the generating series s(x).

  http://paulhankin.github.io/Fibonacci/


Given n, we can extract the value of fib(n) from this expansion by picking an integer A large enough that there is no such overflow (strictly speaking, it's A(n), since it depends on n), multiplying by A**n, and extracting the unit term by considering the rest modulo A:

 A**n*G(1/A)
= A**n*Sum(0<=k)(fib(k)*A**-k)
= Sum(0<=k)(fib(k)*A**(n-k))
= Sum(0<=k<=n)(fib(k)*A**(n-k)) + Sum(n<k)(fib(k)*A**(n-k))
= fib(0)/A**(n-0) + fib(1)/A**(n-1) + ... + fib(n)*A**0 + Sum(n<=k)(fib(k)*A**(n-k))
A**n*G(1/A)
= A**n*(1/A)/(1-(1/A)-1/(A**2))
= A**n*(1/A)*A**2/(A**2*((1-(1/A)-1/(A**2))))
= A**(n+1)/(A**2-A-1) =


Assuming for now that the last term will be less than 1, we have the euclidian division (where the euclidian division div is the lisp operator FLOOR):

 Sum(0<=k<=n)(fib(k)*A**(n-k)) = A**(n+1) div (A**2-A-1)


Then, modulo A, all the terms of the sum disappear except for k=n, and we find this surprising closed formula:

 fib(n) = (A**(n+1) div (A**2-A-1)) mod A


In practice, A=10**n works. Where div is euclidian division:

 fib(n) = (10**(n*(n+1)) div (10**(2*n)-10**n-1)) mod 10**n


The above is remarkable because it's a closed form formula: it has no explicit recursion; all the recursion is done implicitly in the exponent function. Another remarkable thing is that before it extracts fib(n) from the low digits, it computes all the earlier fib(i) in the higher digits in a big expansion, a very large number with about n*(n+1) digits. This gives exact answers, but is very inefficient.

For a little bit of efficiency improvement, we see that A=2**n also works, at least for n>=2. Exponents of 2 can be computed cheaply with ASH, and modulo A becomes bit access using LDB. We add a fudge term to fix the computation for n=1.

 fib(n) = ((2**(n*(n+1))+1) div (2**(2*n)-2**n-1)) mod 2**n


How small can we make A?

For the terms after n to sum under 1, we need to choose A large enough that

  s = Sum(n<k)(fib(k)*A**(n-k)) < 1


We can check manually that the minimum A's for small n are:

  A(0)=3, A(1)=3, A(2)=4, A(3)=5, A(4)=7, A(5)=10, A(6)=15, A(7)=23...


From the previous closed formula (see function rfib), we know that Therefore, with k=n+1+l, we have

  s = Sum(n<k)(fib(k)*A**(n-k))
= Sum(0<=l)(fib(n+1+l)*A**-(1+l))
< Sum(0<=l)((phi**n/sqrt(5))*(phi/A)**(1+l)
= phi**n/sqrt(5)*(phi/A)/(1-phi/A)
= phi**(n+1)/sqrt(5)/A/(1-phi/A)
= phi**(n+1)/sqrt(5)/(A-phi)
<= 1


We can solve that as such:

  A-phi >= phi**(n+1)/sqrt(5)
A >= phi + phi**(n+1)/sqrt(5)


But to get A=2**k, and k>=4, it's easier to approximate A from above with:

  A >= phi**(n+1)/sqrt(5)/(1-phi/16) > phi**(n+1)/sqrt(5)/(1-phi/A)
k >= log(phi**(n+1)/sqrt(5)/(1-phi/16))/log(2)
k >= n*log(phi)/log(2) + log(phi/(sqrt(5)*(1-phi/16)))/log(2)
k >= n*log(phi)/log(2) + B


with

  B = log(phi/(sqrt(5)*(1-phi/16)))/log(2) = -0.31291115520113505...


then we can approximate k from above by using a rational number C/D that is strictly larger than log(phi)/log(2), at which point we use

  k = ceiling((n*C+ceiling(B*D))/D)
A = 2**k


Now, we've optimized the number of bits of precision needed, but we still have this very unwieldly division of an overly large number that contains way more digits than needed. Wouldn't it be nice to simplify the formula so that we don't have to do that much computations, using only modular operations?

First note that when we have a euclidian division,

  Sum(0<=k<=n)(fib(k)*A**(n-k)) = A**(n+1) div (A**2-A-1)


and we call the quotient q and the remainder r, then we have the exact formula:

  A**(n+1) = q * (A**2-A-1) + r


then modulo A, we have

  0 = q*-1 + r (mod A)


or

  q = r (mod A)


and since q = fib(n) (mod A), we find the closed formula:

  fib(n) = (A**(n+1) mod (A**2-A-1)) mod A


This is once again a remarkable closed formula, and this time, we only need modular exponentiation, and this formula, in addition to being closed, leads to an efficient algorithm with the correct asymptotic behavior!

## What happened to the Latin-based languages?

There used to be versions of this wiki site on the Fibonacci numbers in French, Italian, Portuguese, Spanish... I found them but they are not linked to this particular site. What happened? These links should be restored.TonyMath (talk) 06:01, 27 September 2016 (UTC)

Wikidata made a stupid split between Fibonacci number (Q47577) and Fibonacci series (Q23835349) depending on how the article happens to be titled in each language. The articles are about exactly the same and no language has two separate articles so there is no reason for the split. They should be merged. PrimeHunter (talk) 11:55, 27 September 2016 (UTC)
I'm not sure about Wikidata merge policies when Fibonacci series (Q23835349) has statements that may not apply to Fibonacci number (Q47577), but I have moved all the language links to the latter. Let's hope they stay there. PrimeHunter (talk) 12:21, 28 September 2016 (UTC)
They were quickly split again and I got no support at wikidata:User talk:Infovarius#Fibonacci number/series. I haven't found a Wikidata process for proposed mergers. PrimeHunter (talk) 11:02, 3 October 2016 (UTC)
The numbers of the Fibonacci sequence are related to each other via the (famous) recursion formula ${\displaystyle a_{n+1}=a_{n}+a_{n-1}}$ with ${\displaystyle a_{0}=0}$ and ${\displaystyle a_{1}=1}$. You cannot have the numbers without the sequence and you cannot have the sequence without the numbers. There should be no split. TonyMath (talk) 19:48, 5 October 2016 (UTC)

## Fibonacci in Nature

Any more elaboration on this topic? Shyla Kannambadi (talk) 04:58, 3 January 2017 (UTC)

## Closed form and Binet formula

The formula given for the Binet formula is not the same as the one given on Binet's page.

${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}\neq {\frac {(1+{\sqrt {5}})^{n}-(1-{\sqrt {5}})^{n}}{2^{n}{\sqrt {5}}}}}$

And also ${\displaystyle \varphi -\psi =1\neq 2{\sqrt {5}}}$ — Preceding unsigned comment added by 84.226.134.142 (talkcontribs) 09:27, 14 January 2017 (UTC)

If you substitute ${\displaystyle \varphi }$ and ${\displaystyle \psi }$ for their values, a very simple transformation allows passing from the first formula to the second one (factoring the denominators 2 out of the exponentiations, and putting them as a common denominator). Also ${\displaystyle \varphi -\psi ={\sqrt {5}},}$ not 1, nor ${\displaystyle 2{\sqrt {5}}.}$ So the two given formulas are correct and equivalent. D.Lazard (talk) 10:43, 14 January 2017 (UTC)