Periodic Coefficients and Random Fibonacci Sequences

Karyn McLellan

Abstract


The random Fibonacci sequence is defined by $t_1 = t_2 = 1$ and $t_n = \pm t_{n-1} + t_{n-2}$, for $n \geq 3$, where each $\pm$ sign is chosen at random with probability $P(+) = P(-) = \frac{1}{2}$. Viswanath has shown that almost all random Fibonacci sequences grow exponentially at the rate $1.13198824\ldots$. We will consider what happens to random Fibonacci sequences when we remove the randomness; specifically, we will choose coefficients which belong to the set $\{1, -1\}$ and form periodic cycles. By rewriting our recurrences using matrix products, we will analyze sequence growth and develop criteria based on eigenvalue, trace and order for determining whether a given sequence is bounded, grows linearly or grows exponentially. Further, we will introduce an equivalence relation on the coefficient cycles such that each equivalence class has a common growth rate, and consider the number of such classes for a given cycle length.

Keywords


random Fibonacci sequence; growth rate; periodic; matrix trace

Full Text: PDF