##
**
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 *g*_{n} =
|*g*_{n-1} ± *g*_{n-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**