Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Random Fibonacci sequences and the number $1.13198824\dots$
HTML articles powered by AMS MathViewer

by Divakar Viswanath PDF
Math. Comp. 69 (2000), 1131-1155 Request permission


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
Additional Information
  • Divakar Viswanath
  • Affiliation: Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, California 94720
  • Email:
  • Received by editor(s): November 17, 1997
  • Received by editor(s) in revised form: July 14, 1998
  • Published electronically: 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 2000 American Mathematical Society
  • Journal: Math. Comp. 69 (2000), 1131-1155
  • MSC (1991): Primary 15A52, 28A80, 60J05, 65G05
  • DOI:
  • MathSciNet review: 1654010