eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/7304
Title:  Random Fibonacci sequences and the number 1.13198824... 
Authors:  Viswanath, Divakar 
Keywords:  computer science technical report 
Issue Date:  Oct1997 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR971650 
Abstract:  \begin{abstract} For the familiar Fibonacci sequence  defined by $f_1 = f_2 = 1$, and $f_n = f_{n1} + f_{n2}$ for $n greater than 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 {\it random} Fibonacci sequences defined by $t_1=t_2=1$, and for $n greater than 2$, $t_n = \pm t_{n1} \pm t_{n2}$, where each $\pm$ sign is independent and either $+$ or $$ with probability $1/2$  it is not even obvious if $\abs{t_n}$ should increase with $n$. Our main result is that \begin{equation*} \sqrt[n]{\abs{t_n}} \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, SternBrocot division of the real line, a fractallike measure, a computer calculation, and a rounding error analysis to validate the computer calculation. \end{abstract} 
URI:  http://hdl.handle.net/1813/7304 
Appears in Collections:  Computer Science Technical Reports

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
