On the Average Growth of Random Fibonacci Sequences
Benoît Rittaud
Université Paris-13
Institut Galilée
Laboratoire Analyse, Géométrie et Applications
99, avenue Jean-Baptiste Clément
93 430 Villetaneuse
France
Abstract:
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,
dvi,
ps,
latex
(Concerned with sequences
A000032
A000945
A001764
A008998 and
A083404
.)
Received April 21 2006;
revised version received January 18 2007.
Published in Journal of Integer Sequences January 19 2007.
Return to
Journal of Integer Sequences home page
