The Growth Rate of Random Fibonacci-Type Sequences

Hei-Chi Chan University of Illinois at Springfield, USA

Estimating the growth rate of random Fibonacci-type sequences is both challenging and fascinating. In this talk, I will discuss a recent result in this area. Let a denote an infinite sequence of natural numbers {a_{1}, a_{2}, ⋯ } and define a random Fibonacci-type sequence by F_{−1} = 0, F_{0} = 1, a_{0} = 0, and

F_{k} = 2^{a_{k}}F_{k−1} + 2^{a_{k−1}}F_{k−2}

for k ≥ 1. Then, for almost all such infinite sequences a, we have

lim_{n→∞} \frac{ln F_{n}}{n} = 1.30023 · · · .

This result is motivated by the work of Embree, Trefethen, Viswanath and Wright. The main ingredient is the invariant measure of a dynamical system defined on the interval [0, 1).