Talk:Fibonacci sequence

Template:Vital article

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!

See http://fare.tunes.org/files/fun/fibonacci.lisp

Closed form and Binet formula

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

$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 $\varphi -\psi =1\neq 2{\sqrt {5}}$ — Preceding unsigned comment added by 84.226.134.142 (talk • contribs) 09:27, 14 January 2017 (UTC)

Please sign your posts in talk page with four tildes (~~~~).

If you substitute $\varphi$ and $\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 $\varphi -\psi ={\sqrt {5}},$ not 1, nor $2{\sqrt {5}}.$ So the two given formulas are correct and equivalent. D.Lazard (talk) 10:43, 14 January 2017 (UTC)

Shallow Diagonal

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 http://mathworld.wolfram.com/ShallowDiagonal.html. — Preceding unsigned comment added by Scuilion.scuilion (talk • contribs) 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)

Pareto distribution and Fibonacci sequence

Haven't you notice that Fibonacci's sequence are basically the same thing? When I type it in excel and sum first 4/5 and last 1/5 separately I get something around 0,2. I think that this should be mentioned here.

If I discovered it first please call it "KGD's observation". — Preceding unsigned comment added by 89.71.45.86 (talk) 17:16, 13 April 2018 (UTC)

The Pareto distribution is a continuous function that depends on a parameter $\alpha$ and takes its value between 0 and 1. The Fibonacci sequence is a sequence of integers, which grow exponentially. They cannot be basically the same thing. It may be some connexion between them, but this does not results immediately from the definitions, and, if such a connexion exists, it needs more explanation. In any case, even if your observation is correct, the rules of Wikipedia (WP:NOR) makes that it cannot be mentioned here, unless it is regularly published in a mathematics journal. D.Lazard (talk) 17:53, 13 April 2018 (UTC)

Intelligent Design

Why is there nothing in this article discussing the theory that, FN is possible proof of a creator? I find that troubling. Is there another article about this topic? Jsderwin (talk) 17:05, 28 April 2018 (UTC)

This article is about mathematics, not about theology. D.Lazard (talk) 17:12, 28 April 2018 (UTC)

So maybe there should be a disambiguation page. Jsderwin (talk) 17:24, 28 April 2018 (UTC)

Perhaps Jsderwin should be redirected to a relevant but made-up anecdote. —David Eppstein (talk) 17:39, 28 April 2018 (UTC)

David, can you stick to the point? Thanks. Jsderwin (talk) 18:27, 28 April 2018 (UTC)