Summary: We prove that the average value of the $n$-th term of a sequence defined by the recurrence relation $g_{n} = |g_{n-1} \pm g_{n-2}$|, where the $\pm $ 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.

11A55, 15A52, 05C05, 15A35

binary tree, random Fibonacci tree, linear recurring sequence, random Fibonacci sequence, continued fraction