A Probabilistic Approach to the Fibonacci Sequence
- PDF / 417,132 Bytes
- 5 Pages / 593.972 x 792 pts Page_size
- 50 Downloads / 226 Views
ne of the fascinating things about the Fibonacci sequence is that the values quickly approach a particular exponential function. In this work, the constants of this limiting function are explained through the limiting distribution of a Markov chain that encapsulates the entire Fibonacci sequence. In his text Liber Abaci [5], Fibonacci used the sequence that now bears his name to illustrate the power of the Hindu–Arabic system of place-value notation, which, he set out to demonstrate, made it superior to Roman numerals in calculating the rapidly growing terms of the sequence. Computation reveals that the sequence rapidly approaches a particular exponential function. This raises the question of why such a limiting function exists, and why the function has the constants that is has. The limiting function is easy to verify, but in this work we give a novel explanation: it is related to the limiting distribution of a Markov chain. A Markov chain is an infinite sequence of random variables X0 ; X1 ; X2 ; . . . such that given X0 ; . . .; Xt , the distribution of Xtþ1 depends only on Xt and not on any of the prior states. The powerful ergodic theorem gives simple conditions under which the distribution of the state Xt approaches a limiting distribution that can be calculated. This is, for instance, why virtually every method of shuffling a deck of cards leads to an approximately uniform distribution over all possible permutations of the cards. Or
O
randomly twisting sides of a Rubik’s cube leads to an approximately uniform distribution over the set of solvable states. In this work, a connection will be made, first introduced by Benjamin et al. [1], between the limiting behavior of the Fibonacci sequence and a Markov chain that encodes the entire sequence. The limit theorem for Fibonacci growth then becomes just an application of the ergodic theorem.
The Fibonacci Sequence Let F1 ¼ F2 ¼ 1, and for n [ 2, let Fn ¼ Fn1 þ Fn2 : This sequence was introduced to Europeans by Leonardo of Pisa—better known as Fibonacci—in order to illustrate the power of calculating with decimal arithmetic. Five hundred years after Fibonacci, Abraham de Moivre developed a theory for solving general linear recurrences [3] and gave the first explicit formula for the values of the Fibonacci sequence: Fn ¼
/n ð/Þn pffiffiffi ; 5
pffiffiffi where / ¼ 1 þ 5 =2 is the golden ratio. The golden ratio has been studied since at least the time of Euclid (see [2]), providing an interesting link between this simple recurrence and geometry. This formula was later rediscovered by Jacques Binet, and so also goes by the name of Binet’s formula. This
Ó 2019 Springer Science+Business Media, LLC, part of Springer Nature https://doi.org/10.1007/s00283-019-09950-3
formula immediately gives the limiting behavior of the Fibonacci sequence:
the rest of the nodes? Using the conditional probability formula, we see that
Fn 1 ¼ pffiffiffi : n n!1 / 5
PððB1 ; . . .; Bn Þ ¼ ðb1 ; b2 ; b2 ; . . .; bn Þ j Bnþ1 ¼ 0Þ
lim
Representing the Sequence Combinatorially In a graph, an i
Data Loading...
