On the Average Growth of Random Fibonacci Sequences
Laboratoire Analyse, Géométrie et Applications
99, avenue Jean-Baptiste Clément
93 430 Villetaneuse
We prove that the average value of the n-th term of a sequence
defined by the recurrence relation gn =
|gn-1 ± gn-2|, where
the ± sign is randomly chosen, increases exponentially, with a
growth rate given by an explicit algebraic number of degree 3. The
proof involves a binary tree such that the number of nodes in each row
is a Fibonacci number.
Full version: pdf,
(Concerned with sequences
Received April 21 2006;
revised version received January 18 2007.
Published in Journal of Integer Sequences January 19 2007.
Journal of Integer Sequences home page