Periodic coefficients and random Fibonacci sequences (Q396963)

Summary: 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.