Talk:Fibonacci number

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, High-importance)
WikiProject Mathematics
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[edit]

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

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

Extracting closed-forms from generating function's power series[edit]

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

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*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*(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


  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)


  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?[edit]

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 with and . 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[edit]

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

Closed form and Binet formula[edit]

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

And also — Preceding unsigned comment added by (talkcontribs) 09:27, 14 January 2017 (UTC)

Please sign your posts in talk page with four tildes (~~~~).
If you substitute and 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 not 1, nor So the two given formulas are correct and equivalent. D.Lazard (talk) 10:43, 14 January 2017 (UTC)

Shallow Diagonal[edit]

The definition of "Shallow Diagonal" seems to be undefined. There is a picture, which is helpful, but no definition (or clarification). Wolfram has a page but with no added definition — Preceding unsigned comment added by Scuilion.scuilion (talkcontribs) 21:47, 2 July 2017 (UTC)

The reason you can't find a definition most likely has to do with the fact that there is no "standard" way to write Pascal's triangle–spacing between numbers in a row, spacing between rows, left justified, written as a pyramid, etc. Formulas can be found for writing Fibonacci numbers in terms of binomial coefficients that correspond to these "shallow diagonals", but if you are looking for a quick and dirty description with geometric overtones those formulas just don't appeal. If you insist on a geometric description of a shallow diagonal (in this setting) you could try this ... if the lines through the triangle that are parallel to the sides of the triangle and intersect each row are called diagonals, then a shallow diagonal would be a line with half the slope of a diagonal that intersects every other row. This isn't really precise enough to be a definition and there are special cases to consider (say the diagonals are vertical for instance). If you want precision, use the formula, otherwise you need to settle for the imprecise visualization. --Bill Cherowitzo (talk) 03:19, 3 July 2017 (UTC)