2005/10/07 by Eran Makover, Makover, Eran, Jeffrey McGowan +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Fractal and DNA sequence analysis #Mathematical Dynamics and Fractals #math.NT #msc:11B39
paper · pdf · doi:10.48550/arxiv.math/0510159
7 pages, 2 figures
arxiv created 2005/10/28 · arxiv updated 2009/12/01
We consider random Fibonacci sequences given by xn+1=± βxn+xn-1. Viswanath (\citeviswanath), following Furstenberg (\citefurst) showed that when β= 1, limn→ ∞|xn|1/n=1.13..., but his proof involves the use of floating point computer calculations. We give a completely elementary proof that 1.25577 ≥ (E(|xn|))1/n ≥ 1.12095 where E(|xn|) is the expected value for the absolute value of the nth term in a random Fibonacci sequence. We compute this expected value using recurrence relations which bound the sum of all possible nth terms for such sequences. In addition, we give upper an lower