random Fibonacci sequence

A random Fibonacci sequenceMathworldPlanetmath has its initial terms defined as F0=F1=1 but the sign (plus or minus) in recurrence relation Fn=Fn-1±Fn-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 sequenceMathworldPlanetmath, 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), |Fn|Vn, where |x| is the absolute valueMathworldPlanetmathPlanetmathPlanetmath function, x 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 |Fn|<2 (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 sequenceMathworldPlanetmath, the bigger N is, the closer the absolute value of the Nth number gets to the Nth power of 1.13198824…” (Devlin, 1999) In terms of limits,



  • 1 Keith Devlin, “Devlin’s Angle: New Mathematical Constant Discovered” March 1999 MAA Online
  • 2 Divakar Viswanath “Random Fibonacci sequences and the number 1.13198824….” Mathematics of Computation 69 231 (2000): 1131 - 1155
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