An elementary proof that random Fibonacci sequences grow exponentially
| dc.creator | Makover, Eran | |
| dc.creator | McGowan, Jeffrey | |
| dc.date | 2005-10-07 | |
| dc.date | 2005-10-28 | |
| dc.date.accessioned | 2026-07-07T06:47:13Z | |
| dc.date.available | 2026-07-07T06:47:13Z | |
| dc.description | We consider random Fibonacci sequences given by $x_{n+1}=\pm βx_{n}+x_{n-1}$. Viswanath (\cite{viswanath}), following Furstenberg (\cite{furst}) showed that when $β= 1$, $\lim_{n\to \infty}|x_{n}|^{1/n}=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 | |
| dc.description | 7 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/math/0510159 | |
| dc.identifier | http://arxiv.org/abs/math/0510159 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/103586 | |
| dc.subject | Number Theory | |
| dc.subject | 11B39 | |
| dc.title | An elementary proof that random Fibonacci sequences grow exponentially | |
| dc.type | text |