Periodic coefficients and random Fibonacci sequences

Karyn McLellan¹

¹Dalhousie University

The electronic journal of combinatorics, Tome 20 (2013) no. 4

Résumé

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.

Détail

DOI : 10.37236/3204

Classification : 11B39, 05A05, 15B36
Mots-clés : random Fibonacci sequence, growth rate, periodic, matrix trace