Journal of Integer Sequences, Vol. 10 (2007), Article 07.2.4

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


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