random Fibonacci sequence

A random Fibonacci sequence has its initial terms defined as $F_0=F_1=1$ but the sign (plus or minus) in recurrence relation $F_n=F_{n-1}\pm F_{n-2}$ is chosen randomly with either sign having an equal probability of being chosen. For example, if the random selection gives two minuses followed by three plusses, another minus, etc., the resulting random Fibonacci sequence is 1, 1, 0, $-1$, $-1$, $-2$, $-3$, $-1$, etc. The scenarios that either plus or minus is always consistently chosen leads to the standard Fibonacci sequence, though in the latter case with all values (except the first two) multiplied by $-1$.

In 2000, Divakar Viswanath proved that for most random Fibonacci sequences (with a few notable exceptions), $|F_n|\approx \lfloor V^n\rfloor$, where $|x|$ is the absolute value function, $\lfloor x\rfloor$ is the floor function and $V$ is the constant 1.13198824… now known as Viswanath’s constant. This does not hold true for the standard Fibonacci sequence nor for random Fibonacci sequences for which all (such as 1, 1, 0, 1, $-1$, 0, $-1$, 1, 0, 1, $-1$, generated by consistently alternating plus and minus at each turn), but for almost all other possible random Fibonacci sequences, “you can safely bet your life on the fact that for your sequence, the bigger $N$ is, the closer the absolute value of the $N$th number gets to the $N$th power of 1.13198824…” (Devlin, 1999) In terms of limits,

$$\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{|F_n|}=V.$$

Title	random Fibonacci sequence
Canonical name	RandomFibonacciSequence
Date of creation	2013-03-22 18:09:29
Last modified on	2013-03-22 18:09:29
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	6
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 11B39