An elementary proof that random Fibonacci sequences grow exponentially

Abstract

We consider random Fibonacci sequences given by $x_{n+1}=\pm \beta x_n+x_{n-1}$. Viswanath (\cite{viswanath}), following Furstenberg (\cite{furst}) showed that when $\beta =1$, ${\lim }_{n\to \infty }|x_n{|}^{1/n}=\mathrm{1.13...}$, but his proof involves the use of floating point computer calculations. We give a completely elementary proof that $1.25577\ge (E(|x_n|){)}^{1/n}\ge 1.12095$ where $E(|x_n|)$ is the expected value for the absolute value of the $n$th term in a random Fibonacci sequence. We compute this expected value using recurrence relations which bound the sum of all possible $n$th terms for such sequences. In addition, we give upper an lower

7 pages, 2 figures