Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

Random Fibonacci sequences and the number $1.13198824\ldots$

Author(s): Divakar Viswanath.
Journal: Math. Comp. 69 (2000), 1131-1155.
MSC (1991): Primary 15A52, 28A80, 60J05, 65G05
Posted: June 10, 1999
Retrieve article in: PDF
This article is available free of charge

Abstract | Similar articles | Additional information

Abstract: For the familiar Fibonacci sequence (defined by $f_1 = f_2 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n>2$), $f_n$ increases exponentially with $n$ at a rate given by the golden ratio $(1+\sqrt{5})/2=1.61803398\ldots$. But for a simple modification with both additions and subtractions - the random Fibonacci sequences defined by $t_1=t_2=1$, and for $n>2$, $t_n = \pm t_{n-1} \pm t_{n-2}$, where each $\pm$ sign is independent and either $+$ or - with probability $1/2$ - it is not even obvious if $\vert{t_n}\vert$ should increase with $n$. Our main result is that

\begin{equation*}\sqrt[n]{\vert{t_n}\vert} \rightarrow 1.13198824\ldots\:\:\: \text{as}\:\:\: n \rightarrow\infty \end{equation*}

with probability $1$. Finding the number $1.13198824\ldots$ involves the theory of random matrix products, Stern-Brocot division of the real line, a fractal measure, a computer calculation, and a rounding error analysis to validate the computer calculation.


Similar Articles:

Retrieve articles in Mathematics of Computation with MSC (1991): 15A52, 28A80, 60J05, 65G05

Retrieve articles in all Journals with MSC (1991): 15A52, 28A80, 60J05, 65G05


Additional Information:

Divakar Viswanath
Affiliation: Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, California 94720
Email: divakar@cs.cornell.edu

DOI: 10.1090/S0025-5718-99-01145-X
PII: S 0025-5718(99)01145-X
Received by editor(s): November 17, 1997
Received by editor(s) in revised form: July 14, 1998
Posted: June 10, 1999
Additional Notes: This work was supported in part by NSF Grant DMS-9500975CS and DOE Grant DE-FG02-94ER25199 to Lloyd N. Trefethen.
Copyright of article: Copyright 2000, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google