<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{graphs}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf On the Average Growth of Random\\
\vskip .1in
Fibonacci Sequences
}
\vskip 1cm
\large
Beno\^{\i}t Rittaud\\
Universit\'e Paris-13 \\
Institut Galil\'ee \\
Laboratoire Analyse, G\'eom\'etrie et Applications \\
99, avenue Jean-Baptiste Cl\'ement \\
93~430 Villetaneuse\\
France\\
\href{mailto:rittaud@math.univ-paris13.fr}{\tt rittaud@math.univ-paris13.fr}
\end{center}

\vskip .2 in

\begin{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}\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.
\end{abstract}

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{proposition}{Proposition}[section]
%\newtheorem{corollary}{Corollary}[section]
%\newtheorem{lemma}{Lemma}[section] 


\def\R{\mathbb R}
\def\E{\mathbb E}
\def\C{\mathbb C}
\def\Z{\mathbb Z}
\def\N{\mathbb N}
\def\Card{\mbox{\rm Card}}
\def\SL{\mbox{\rm SL}}

\newtheorem{theorem}{Theorem}
\newtheorem{Def}{Definition}
\newtheorem{Rem}{Remark}
\newtheorem{Prop}{Proposition}
\newtheorem{Cor}{Corollary}
\newtheorem{Notation}{Notation}
\newtheorem{Lemme}{Lemma}


\section{Introduction}


A {\em random Fibonacci sequence} is  a sequence $(g_{n})_{n}$ in
which $g_{0}$ and $g_{1}$ are arbitrary nonnegative 
real numbers and such that, for any
$n\geq 2$, one has $g_{n}=|g_{n-1}\pm g_{n-2}|$, where the $\pm$ sign 
is randomly chosen for each $n$.

In 2000, Divakar Viswanath \cite{Viswanath} proved
 that, in the set of random Fibonacci sequences
equipped with the natural probabilistic structure $(1/2,
1/2)^{\otimes\N}$, almost all random Fibonacci sequences are
exponentially growing, with a growth rate equal to $1.13198824\ldots$. Up to
now, no analytic expression for this value was known.

In 2005, Jeffrey McGowan and Eran Makover
 \cite{McGowanMakover} used an elementary idea to evaluate the growth 
 rate of the average
value of the $n$-th term of a Fibonacci sequence, using the formalism of
trees. Thanks to Jensen's
inequality, this second growth rate is necessarily bigger than the
value $1.13198824\ldots$, which appears in Viswanath's study, since
this latter value corresponds to a growth rate in an almost-sure sense.

The first goal of the present article is to give an algebraic
expression for the growth rate of the average of the $n$-th term of a
random Fibonacci sequence. We use the formalism of trees, refining the
McGowan-Makover construction \cite{McGowanMakover}, by considering the full
binary tree of all possible random Fibonacci sequences starting from
two fixed initial values. Our main result is the following

\begin{theorem}\label{Main1}  For any fixed $g_{0}$ and $g_{1}$ (not both equal
to zero), let us define $m_{n}$ as the mean value of the $n$-th term of a
random Fibonacci sequence starting from $g_{0}$ and $g_{1}$. Then, the
ratio $m_{n+1}/m_{n}$
tends to $\alpha-1\approx 1.20556943$ as $n$ goes to infinity, 
where $\alpha\approx 2.20556943$ is the 
only real number for which $\alpha^3=2\alpha^2+1$.
\end{theorem}

Let $a$ and $b$ be  nonnegative real numbers. 
By the {\em random Fibonacci tree of the pair $(a,b)$}, 
we mean the binary tree
denoted by ${\mathbf{T}}_{(a,b)}$ and 
defined in the following way: $a$ is the root, $b$ its only child; if 
$x$ is the parent of $y$, then $y$ has two children, which are $x+y$
and $|x-y|$. In other words, the possible walks in the tree
${\mathbf{T}}_{(a,b)}$ 
give the full list of random Fibonacci sequences $(g_{n})_{n}$ such 
that $g_{0}=a$ and $g_{1}=b$. In this formalism, the sequence $(m_{n})_{n}$ 
can be characterized by the equality $m_{n}=S_{n}/2^n$, where $S_{n}$ 
is the sum of all values in the $n$-th row of the tree.

The study of the sequence $(S_{n})_{n}$ is made by considering another
binary tree, which we will call the {\em restricted random 
Fibonacci tree}, denoted by
${\mathbf{R}}_{(a,b)}$, which is the subtree of ${\mathbf{T}}_{(a,b)}$ 
obtained by cutting
all redundant edges (a precise definition and the first few rows of
${\mathbf{R}}_{(1,1)}$ are given in subsection \ref{restricted}). 
This subtree, which to our knowledge
has never been studied before, seems to have many
interesting properties -- in fact, it seems that it is even more
interesting than random Fibonacci trees.

The present paper is organized in the following way: in section 1
we introduce basic facts about trees and initiate the study of the
tree ${\mathbf{R}}={\mathbf{R}}_{(1,1)}$ in view of Theorem \ref{Main1}. 
Section 2 is devoted to the proof of Theorem \ref{Main1}. In section
3, we investigate more 
properties of the tree ${\mathbf{R}}$, which has many arithmetical 
aspects that  are of interest. In
this section, we 
also focus our interest in some other trees derived from ${\mathbf{R}}$.
In section 4, we give some open questions and a heuristic formula which
gives a 
link between trees ${\mathbf{T}}$ and ${\mathbf{R}}$. This latter 
formula will be proved in another
article \cite{EBT}, where the question of the growth rate of almost
all random Fibonacci sequences is considered.




\section{Definitions and fundamental results about trees}


We start with a few simple relevant facts about trees that are of interest
for us.

\subsection{The tree ${\mathbf{T}}$}


It is easily shown that, for any positive numbers $a$, $b$ and $c$, the
trees ${\mathbf{T}}_{(ca,cb)}$ and ${\mathbf{T}}_{(a,b)}$ have the same
nodes up to the multiplicative constant $c$, so, when  $a$ and $b$ are
integers (the only case of interest for us in this section), it is not
restrictive to assume that $a$ and $b$ are relatively prime.
Proposition \ref{Containment} will show that it is, in fact, enough to
focus our attention on ${\mathbf{T}}_{(1,1)}$, which will simply be
denoted by ${\mathbf{T}}$ in the following.


A pair $(a,b)$ of natural numbers is said to  {\em appear in
${\mathbf{T}}$} (or, simply, {\em appears}) whenever there exists a node in
${\mathbf{T}}$ 
of value $a$ with a child of value $b$.


\begin{Lemme}\label{Uns}  There exist two walks in ${\mathbf{T}}$, denoted
by $1^-$ and $1^+$, such that $1^-$ is exactly composed of all the
pairs
of the form $(1,2n+1)$ and $(2n,1)$ ($n$ an integer) and $1^+$ composed
of all the pairs of the form $(2n+1,1)$ and $(1,2n)$.
\end{Lemme}

\begin{proof} We start from $g_{0}=g_{1}=1$ and $g_{2}=2$. A
trivial calculation shows that, for all $k\geq 2$, defining $g_{k}$
by:
\[g_{k}=\left\{\begin{array}{ll}g_{k-1}+g_{k-2},&amp;\mbox{if $k\equiv 1$ or
$2$ (mod $3$);}\\
g_{k-1}-g_{k-2},&amp;\mbox{if $k\equiv 0$ (mod $3$);}
\end{array}\right.\]
\noindent gives the walk $1^-$. In the same way, if, for $k\geq 2$,
we define $g_{k}$ as:
\[g_{k}=\left\{\begin{array}{ll}g_{k-1}+g_{k-2},&amp;\mbox{if $k\equiv 0$ or
$2$ (mod $3$);}\\
g_{k-1}-g_{k-2},&amp;\mbox{if $k\equiv 1$ (mod $3$);}
\end{array}\right.\]
\noindent then we get $1^+$.
\end{proof}


\begin{Prop}\label{Containment}  A pair of 
positive integers $(a,b)$ appears in ${\mathbf{T}}$ if and
only if $a$ and $b$ are relatively prime. 
In ${\mathbf{T}}$, the only appearing pair of integers
$(a,b)$ with $ab=0$ are $(0,1)$ and $(1,0)$.

\end{Prop}


\begin{proof} We start by proving the second part. If, 
for example, 
$a=0$ and $b\neq 0$ are such that $(a,b)$ appears, then, the parent 
of $0$ is $b$, the parent of this parent is $b$
again, then either $0$ or $2b$, etc. In any case, we get multiples of 
$b$ as successive ancestors; since the beginning of
${\mathbf{T}}$ is $1-1-0$, we must have $b=1$.

Let us prove now the first part. A pair $(a,b)$ appearing in ${\mathbf{T}}$ 
being given such that 
$ab\neq 0$, let $d$ be the greatest common divisor of $a$ and $b$. Let $z$ be the
parent of $a$. Since we have $b=|z-a|$ or $b=z+a$, $d$ is also the
greatest  
common divisor of $z$ and $a$. By induction, $d$ is the greatest
common divisor of $1$ (the root
of ${\mathbf{T}}$), and $1$ (the child of the root), so $d=1$.

Conversely, let $a\neq b$ be two relatively prime integers. We input
them to the Euclidean algorithm:
we write $r_{0}$ for $a$, $r_{1}$ for $b$ and, for any $i\geq 0$ such 
that $r_{i+1}\neq 0$, we define
$r_{i+2}$ as the only integer in $[0, r_{i+1}[$ for which there exists
an integer $n_{i}$ such that $r_{i}=n_{i}r_{i+1}+r_{i+2}$. Let us
denote by $N$ the index such that $r_{N}=0$. Since $a$ and $b$ are
relatively prime, we have $r_{N-1}=1$ so, thanks to Lemma \ref{Uns}, the
pairs $(r_{N-1},r_{N-2})$ and $(r_{N-2},r_{N-1})$ both appear in
${\mathbf{T}}$.

Let assume now that the pairs $(r_{i+1},r_{i})$ and
$(r_{i},r_{i+1})$ both appear, for an $i\leq N-2$.

Starting from
$(r_{i+1},r_{i})$, we consider the walk obtained by two additions, one 
subtraction, again two additions, one subtraction, etc. This gives the
sequence $r_{i+1}$, $r_{i}$, $r_{i}+r_{i+1}$, $2r_{i}+r_{i+1}$,
$r_{i}$, $3r_{i}+r_{i+1}$, etc. so the proof splits in two cases: if
$n_{i-1}$ is odd, then we obtain the pair
$(r_{i}, n_{i-1}r_{i}+r_{i-1})=(r_{i},r_{i-1})$. If $n_{i-1}$ is even,
then we obtain the pair $(r_{i}, (n_{i-1}-1)r_{i}+r_{i+1})$, that
is, $(r_{i}, r_{i-1}-r_{i})$. The next elements of the walk are, then,
$r_{i}+(r_{i-1}-r_{i})=r_{i-1}$, then
$|r_{i-1}-(r_{i-1}-r_{i})|=r_{i}$, so we get the pair
$(r_{i-1},r_{i})$.

Similar reasoning holds when we start from $(r_{i},r_{i+1})$. One
addition, one subtraction, then two additions, one subtraction, two 
additions, one subtraction, etc. gives the sequence $r_{i}$,
$r_{i+1}$, $r_{i}+r_{i+1}$, $r_{i}$, $2r_{i}+r_{i+1}$,
$3r_{i}+r_{i+1}$, $r_{i}$, $4r_{i}+r_{i+1}$, etc., so if $n_{i-1}$ is 
even we finally get the pair $(r_{i},r_{i-1})$. If $n_{i-1}$ is odd,
we get the pair $(r_{i},r_{i-1}-r_{i})$. An addition followed by a
subtraction then gives the pair $(r_{i-1},r_{i})$.

In conclusion, starting from $(r_{i+1},r_{i})$ and $(r_{i},r_{i+1})$
respectively, we obtain $(r_{i},r_{i-1})$ and $(r_{i-1},r_{i})$
if $n_{i-1}$ is odd, $(r_{i-1},r_{i})$ and $(r_{i},r_{i-1})$
if $n_{i-1}$ is even, and the proposition is thus proved by induction.
\end{proof}


Recall that $\lfloor x\rfloor$ denotes the integer part of $x$. 
We can sum up the previous construction in the following way:

\begin{itemize}

\item if $n_{i-1}$ is odd, then

\begin{itemize}
\item starting from 
$(r_{i},r_{i+1})$, we attain $(r_{i-1},r_{i})$ in $2+3\cdot
\lfloor n_{i-1}/2\rfloor$ steps;

\item starting from 
$(r_{i+1},r_{i})$, we attain $(r_{i},r_{i-1})$ in $1+3\cdot
\lfloor n_{i-1}/2\rfloor$ steps;
\end{itemize}

\item if $n_{i-1}$ is even, then

\begin{itemize}
\item starting from 
$(r_{i},r_{i+1})$, we attain $(r_{i},r_{i-1})$ in $3n_{i-1}/2$ steps;

\item starting from 
$(r_{i+1},r_{i})$, we attain $(r_{i-1},r_{i})$ in $3n_{i-1}/2$ steps.
\end{itemize}

\end{itemize}

It is easily seen that if the pair $(a,b)$ appears in
${\mathbf{T}}_{(c,d)}$, then the full tree ${\mathbf{T}}_{(a,b)}$ appears in ${\mathbf{T}}_{(c,d)}$,
in an obvious sense. The following shows a ``self-containment'' aspect of
random Fibonacci trees.


\begin{Prop}\label{fractal}  For any positive integers $a$ and $b$
relatively prime, 
${\mathbf{T}}_{(a,b)}$ appears infinitely many times in ${\mathbf{T}}$.
\end{Prop}

\begin{proof}
Proposition \ref{Containment} shows that any pair of the form $(a,b)$
where $a$ and $b$ are relatively prime appears in ${\mathbf{T}}$. It is
then enough to show that ${\mathbf{T}}$ appears in
${\mathbf{T}}_{(a,b)}$. We consider a random Fibonacci sequence
$(g_{n})_{n}$ such that $g_{0}=g_{1}=1$, $g_{n-1}=a$ and $g_{n}=b$ for
an $n$. For  $k&gt;0$, we then define $g_{n+k}$ as
$|g_{n+k-1}-g_{n+k-2}|$.

It is easily seen that, for any integers $u$ and $v$, we
always have $\max(|v-u|,v)\leq \max(v,u)$, with 
equality iff these maxima are both equal to $v$. The equality case
cannot, therefore, occur for 
two successive pairs of $g_{n+k}$. As a consequence, we
get that there is a $k\leq 2n$ such that $g_{n+k}=g_{n+k+1}=1$, and 
we are done.
\end{proof}

As a corollary, we get the following result:

\begin{Cor}  Any pair appearing in ${\mathbf{T}}$ appears infinitely many 
times in ${\mathbf{T}}$.
\end{Cor}



Therefore, if $a$ and $b$ are relatively prime, 
the random Fibonacci tree generated by $a$ with a child $b$
is a subtree of ${\mathbf{T}}$. Recall
that, if this is not the case, and 
$d&gt;1$ is the greatest common divisor of $a$ and
$b$, then ${\mathbf{T}}_{(a,b)}$ is homothetic
to ${\mathbf{T}}_{(a/d,a/d)}$ which, by the
previous proposition, is a subtree of ${\mathbf{T}}$.

Here is the beginning of the random Fibonacci tree ${\mathbf{T}}$. For a node
$a$ with child $b$, the right child of $b$ is $b+a$ and the left child
is $|b-a|$.

\begin{figure}[H]
{\vskip .5in}
{\hskip 1.2in}
\begin{graph}(19,7)(5,0)
\newcommand{\node}[4]{%
\textnode #1(#2,#3){#4}[\graphlinecolour{1}]}
\node{Rac}{10}{8}{1}
\node{FilsRac}{10}{7}{1}
\node{PetitFils1}{5}{6}{0}
\node{PetitFils2}{15}{6}{2}
\node{L2n1}{3}{5}{1}
\node{L2n2}{7}{5}{1}
\node{L3n1}{2}{4}{1}
\node{L3n2}{4}{4}{1}
\node{L3n3}{6}{4}{1}
\node{L3n4}{8}{4}{1}
\node{L4n1}{1.5}{3}{0}
\node{L4n2}{2.5}{3}{2}
\node{L4n3}{3.5}{3}{0}
\node{L4n4}{4.5}{3}{2}
\node{L4n5}{5.5}{3}{0}
\node{L4n6}{6.5}{3}{2}
\node{L4n7}{7.5}{3}{0}
\node{L4n8}{8.5}{3}{2}
\node{L5n1}{1.25}{2}{1}
\node{L5n2}{1.75}{2}{1}
\node{L5n3}{2.25}{2}{1}
\node{L5n4}{2.75}{2}{3}
\node{L5n5}{3.25}{2}{1}
\node{L5n6}{3.75}{2}{1}
\node{L5n7}{4.25}{2}{1}
\node{L5n8}{4.75}{2}{3}
\node{L5n9}{5.25}{2}{1}
\node{L5n10}{5.75}{2}{1}
\node{L5n11}{6.25}{2}{1}
\node{L5n12}{6.75}{2}{3}
\node{L5n13}{7.25}{2}{1}
\node{L5n14}{7.75}{2}{1}
\node{L5n15}{8.25}{2}{1}
\node{L5n16}{8.75}{2}{3}
\node{L6n1}{1.125}{1}{\tiny 1}
\node{L6n2}{1.375}{1}{\tiny 1}
\node{L6n3}{1.625}{1}{\tiny 1}
\node{L6n4}{1.875}{1}{\tiny 1}
\node{L6n5}{2.125}{1}{\tiny 1}
\node{L6n6}{2.375}{1}{\tiny 3}
\node{L6n7}{2.625}{1}{\tiny 1}
\node{L6n8}{2.875}{1}{\tiny 5}
\node{L6n9}{3.125}{1}{\tiny 1}
\node{L6n10}{3.375}{1}{\tiny 1}
\node{L6n11}{3.625}{1}{\tiny 1}
\node{L6n12}{3.875}{1}{\tiny 1}
\node{L6n13}{4.125}{1}{\tiny 1}
\node{L6n14}{4.375}{1}{\tiny 3}
\node{L6n15}{4.625}{1}{\tiny 1}
\node{L6n16}{4.875}{1}{\tiny 5}
\node{L6n17}{5.125}{1}{\tiny 1}
\node{L6n18}{5.375}{1}{\tiny 1}
\node{L6n19}{5.625}{1}{\tiny 1}
\node{L6n20}{5.875}{1}{\tiny 1}
\node{L6n21}{6.125}{1}{\tiny 1}
\node{L6n22}{6.375}{1}{\tiny 3}
\node{L6n23}{6.625}{1}{\tiny 1}
\node{L6n24}{6.875}{1}{\tiny 5}
\node{L6n25}{7.125}{1}{\tiny 1}
\node{L6n26}{7.375}{1}{\tiny 1}
\node{L6n27}{7.625}{1}{\tiny 1}
\node{L6n28}{7.875}{1}{\tiny 1}
\node{L6n29}{8.125}{1}{\tiny 1}
\node{L6n30}{8.375}{1}{\tiny 3}
\node{L6n31}{8.625}{1}{\tiny 1}
\node{L6n32}{8.875}{1}{\tiny 5}
\node{LL2n1}{13}{5}{1}
\node{LL2n2}{17}{5}{3}
\node{LL3n1}{12}{4}{1}
\node{LL3n2}{14}{4}{3}
\node{LL3n3}{16}{4}{1}
\node{LL3n4}{18}{4}{5}
\node{LL4n1}{11.5}{3}{0}
\node{LL4n2}{12.5}{3}{2}
\node{LL4n3}{13.5}{3}{2}
\node{LL4n4}{14.5}{3}{4}
\node{LL4n5}{15.5}{3}{2}
\node{LL4n6}{16.5}{3}{4}
\node{LL4n7}{17.5}{3}{2}
\node{LL4n8}{18.5}{3}{8}
\node{LL5n1}{11.25}{2}{1}
\node{LL5n2}{11.75}{2}{1}
\node{LL5n3}{12.25}{2}{1}
\node{LL5n4}{12.75}{2}{3}
\node{LL5n5}{13.25}{2}{1}
\node{LL5n6}{13.75}{2}{5}
\node{LL5n7}{14.25}{2}{1}
\node{LL5n8}{14.75}{2}{7}
\node{LL5n9}{15.25}{2}{1}
\node{LL5n10}{15.75}{2}{3}
\node{LL5n11}{16.25}{2}{3}
\node{LL5n12}{16.75}{2}{5}
\node{LL5n13}{17.25}{2}{3}
\node{LL5n14}{17.75}{2}{7}
\node{LL5n15}{18.25}{2}{3}
\node{LL5n16}{18.75}{2}{13}
\node{LL6n1}{11.125}{1}{\tiny 1}
\node{LL6n2}{11.375}{1}{\tiny 1}
\node{LL6n3}{11.625}{1}{\tiny 1}
\node{LL6n4}{11.875}{1}{\tiny 1}
\node{LL6n5}{12.125}{1}{\tiny 1}
\node{LL6n6}{12.375}{1}{\tiny 3}
\node{LL6n7}{12.625}{1}{\tiny 1}
\node{LL6n8}{12.875}{1}{\tiny 5}
\node{LL6n9}{13.125}{1}{\tiny 1}
\node{LL6n10}{13.375}{1}{\tiny 3}
\node{LL6n11}{13.625}{1}{\tiny 3}
\node{LL6n12}{13.875}{1}{\tiny 7}
\node{LL6n13}{14.125}{1}{\tiny 3}
\node{LL6n14}{14.375}{1}{\tiny 5}
\node{LL6n15}{14.625}{1}{\tiny 3}
\node{LL6n16}{14.875}{1}{\tiny 11}
\node{LL6n17}{15.125}{1}{\tiny 1}
\node{LL6n18}{15.375}{1}{\tiny 3}
\node{LL6n19}{15.625}{1}{\tiny 1}
\node{LL6n20}{15.875}{1}{\tiny 5}
\node{LL6n21}{16.125}{1}{\tiny 1}
\node{LL6n22}{16.375}{1}{\tiny 7}
\node{LL6n23}{16.625}{1}{\tiny 1}
\node{LL6n24}{16.875}{1}{\tiny 9}
\node{LL6n25}{17.125}{1}{\tiny 1}
\node{LL6n26}{17.375}{1}{\tiny 5}
\node{LL6n27}{17.625}{1}{\tiny 5}
\node{LL6n28}{17.875}{1}{\tiny 9}
\node{LL6n29}{18.125}{1}{\tiny 5}
\node{LL6n30}{18.375}{1}{\tiny 11}
\node{LL6n31}{18.625}{1}{\tiny 5}
\node{LL6n32}{18.875}{1}{\tiny 21}
\edge{Rac}{FilsRac}
\edge{FilsRac}{PetitFils1}
\edge{FilsRac}{PetitFils2}
\edge{PetitFils1}{L2n1}
\edge{PetitFils1}{L2n2}
\edge{PetitFils2}{LL2n1}
\edge{PetitFils2}{LL2n2}
\edge{L2n1}{L3n1}
\edge{L2n1}{L3n2}
\edge{L2n2}{L3n3}
\edge{L2n2}{L3n4}
\edge{L3n1}{L4n1}
\edge{L3n1}{L4n2}
\edge{L3n2}{L4n3}
\edge{L3n2}{L4n4}
\edge{L3n3}{L4n5}
\edge{L3n3}{L4n6}
\edge{L3n4}{L4n7}
\edge{L3n4}{L4n8}
\edge{L4n1}{L5n1}
\edge{L4n1}{L5n2}
\edge{L4n2}{L5n3}
\edge{L4n2}{L5n4}
\edge{L4n3}{L5n5}
\edge{L4n3}{L5n6}
\edge{L4n4}{L5n7}
\edge{L4n4}{L5n8}
\edge{L4n5}{L5n9}
\edge{L4n5}{L5n10}
\edge{L4n6}{L5n11}
\edge{L4n6}{L5n12}
\edge{L4n7}{L5n13}
\edge{L4n7}{L5n14}
\edge{L4n8}{L5n15}
\edge{L4n8}{L5n16}
\edge{L5n1}{L6n1}
\edge{L5n1}{L6n2}
\edge{L5n2}{L6n3}
\edge{L5n2}{L6n4}
\edge{L5n3}{L6n5}
\edge{L5n3}{L6n6}
\edge{L5n4}{L6n7}
\edge{L5n4}{L6n8}
\edge{L5n5}{L6n9}
\edge{L5n5}{L6n10}
\edge{L5n6}{L6n11}
\edge{L5n6}{L6n12}
\edge{L5n7}{L6n13}
\edge{L5n7}{L6n14}
\edge{L5n8}{L6n15}
\edge{L5n8}{L6n16}
\edge{L5n9}{L6n17}
\edge{L5n9}{L6n18}
\edge{L5n10}{L6n19}
\edge{L5n10}{L6n20}
\edge{L5n11}{L6n21}
\edge{L5n11}{L6n22}
\edge{L5n12}{L6n23}
\edge{L5n12}{L6n24}
\edge{L5n13}{L6n25}
\edge{L5n13}{L6n26}
\edge{L5n14}{L6n27}
\edge{L5n14}{L6n28}
\edge{L5n15}{L6n29}
\edge{L5n15}{L6n30}
\edge{L5n16}{L6n31}
\edge{L5n16}{L6n32}
\edge{LL2n1}{LL3n1}
\edge{LL2n1}{LL3n2}
\edge{LL2n2}{LL3n3}
\edge{LL2n2}{LL3n4}
\edge{LL3n1}{LL4n1}
\edge{LL3n1}{LL4n2}
\edge{LL3n2}{LL4n3}
\edge{LL3n2}{LL4n4}
\edge{LL3n3}{LL4n5}
\edge{LL3n3}{LL4n6}
\edge{LL3n4}{LL4n7}
\edge{LL3n4}{LL4n8}
\edge{LL4n1}{LL5n1}
\edge{LL4n1}{LL5n2}
\edge{LL4n2}{LL5n3}
\edge{LL4n2}{LL5n4}
\edge{LL4n3}{LL5n5}
\edge{LL4n3}{LL5n6}
\edge{LL4n4}{LL5n7}
\edge{LL4n4}{LL5n8}
\edge{LL4n5}{LL5n9}
\edge{LL4n5}{LL5n10}
\edge{LL4n6}{LL5n11}
\edge{LL4n6}{LL5n12}
\edge{LL4n7}{LL5n13}
\edge{LL4n7}{LL5n14}
\edge{LL4n8}{LL5n15}
\edge{LL4n8}{LL5n16}
\edge{LL5n1}{LL6n1}
\edge{LL5n1}{LL6n2}
\edge{LL5n2}{LL6n3}
\edge{LL5n2}{LL6n4}
\edge{LL5n3}{LL6n5}
\edge{LL5n3}{LL6n6}
\edge{LL5n4}{LL6n7}
\edge{LL5n4}{LL6n8}
\edge{LL5n5}{LL6n9}
\edge{LL5n5}{LL6n10}
\edge{LL5n6}{LL6n11}
\edge{LL5n6}{LL6n12}
\edge{LL5n7}{LL6n13}
\edge{LL5n7}{LL6n14}
\edge{LL5n8}{LL6n15}
\edge{LL5n8}{LL6n16}
\edge{LL5n9}{LL6n17}
\edge{LL5n9}{LL6n18}
\edge{LL5n10}{LL6n19}
\edge{LL5n10}{LL6n20}
\edge{LL5n11}{LL6n21}
\edge{LL5n11}{LL6n22}
\edge{LL5n12}{LL6n23}
\edge{LL5n12}{LL6n24}
\edge{LL5n13}{LL6n25}
\edge{LL5n13}{LL6n26}
\edge{LL5n14}{LL6n27}
\edge{LL5n14}{LL6n28}
\edge{LL5n15}{LL6n29}
\edge{LL5n15}{LL6n30}
\edge{LL5n16}{LL6n31}
\edge{LL5n16}{LL6n32}
\end{graph}
\caption{
The random Fibonacci tree ${\mathbf{T}}={\mathbf{T}}_{(1,1)}$ }
\end{figure}

Let us mention, without further elaboration, that the sequence of
labels in the tree read in breadth-first order 
($1$, $1$, $0$, $2$, $1$, $1$, $1$, $3$, $1$, $1$, $1$, $1$,
$1$, $3$, $1$, $5$\ldots), gives an example of a {\em 2-regular sequence} in 
the 
terminology given by Allouche and Shallit
\cite{AS1,AS2} (see also section \ref{restricted} of the
present article, after Figure 2).



\subsection{Shortest walks in ${\mathbf{T}}$}

By a shortest walk from the root of ${\mathbf{T}}$ to a pair $(a,b)$ 
appearing in ${\mathbf{T}}$, we mean a random Fibonacci sequence such that there
is an $n$ for which $g_{n}=a$, $g_{n+1}=b$ and $n$ is the smallest
integer for which such a random Fibonacci sequence exists.

\begin{Prop}\label{ShortestWay}  The random Fibonacci
sequence constructed 
in the proof of Proposition \ref{Containment} gives the only shortest 
walk in ${\mathbf{T}}$ from the root to the pair $(a,b)$.
\end{Prop}

\begin{proof} To prove this proposition we need the following

\begin{Lemme}\label{StructAsc}  Let the pair $(a,b)$ appear in
${\mathbf{T}}$. Let us consider the set of all pairs $(c,d)$ of
possible 
 ancestors of $(a+b,a)$ in ${\mathbf{T}}$ such that the
ascending walk from $(a,b)$ to $(c,d)$ does not
show the pair $(a,b)$. For all such
$(c,d)$, there exist four integers, $m$, $m'$, $n$ and $n'$, 
such that $c=ma+nb$ and $d=m'a+n'd$,
$|mn'-m'n|= 1$ (in particular, 
$m$ and $m'$ are relatively prime, and so are $n$ and $n'$) and such that 
$m&gt;m'\Longrightarrow n\geq n'$ and $n&gt;n'\Longrightarrow m\geq m'$.

\end{Lemme}

In this lemma, the ``possible ancestors'' of $(a+b,a)$ are the
pairs of integers appearing in ${\mathbf{T}}$ and having
$(a+b,a)$
as successors. In other words, these are the elements of the set of
all ancestors of all pairs of nodes with value $a+b$ at
parent's position and $a$ for child's position (and, so, $b$
for grandchild).

\begin{proof} The property is routinely 
verified for the first nodes of the ``ascending tree'' starting from
$(a+b,a)$. Let us start from the  pair
$(ma+nb,m'a+n'b)$. The possible parents of
$ma+nb$ are $(m+m')a+(n+n')b$, for which the
required properties are trivially verified, and
$d:=|(m-m')a+(n-n')b|$. Let us consider this second case.

Since $m&gt;m'$ implies $n\geq n'$ and $n&gt;n'$ implies $m\geq m'$, we have $d=
|m-m'|a+|n-n'|b$. In any case, the property 
$|mn'-m'n|= 1$ is verified for $(d,ma+nb)$.

Let us
show now that $|m-m'|&gt;m$ implies $|n-n'|\geq n$ and that $|n-n'|&gt;n$
implies $|m-m'|\geq m$. The symmetry of the problem allows us to prove
only one of these two implications: let us do for example the first one.
We thus assume that $|m-m'|&gt;m$ and wish to prove that $|n-n'|\geq n$.

Since $m$ and $m'$ are integers, the inequality $|m-m'|&gt;m$ implies
that $m'=2m+z$, where $z$ is a positive integer. We thus have $\pm 1= 
mn'-m'n=mn'-(2m+z)n=m(n'-n)-(m+z)n$, so $m(n'-n)=\pm 1+(m+z)n$. First,
if $m\neq 0$, then we get $n'-n = n+\frac{\pm 1+zn}{m}$. 
Since we can assume $n\neq 0$ (else the relation
$|n-n'|\geq n$ is trivial), we have $\pm 1+zn\geq 0$, so the
equality 
$n'-n = n+\frac{\pm 1+zn}{m}$ implies $n'-n\geq n$. Second, if $m=0$, 
then the equality $\pm 1=mn'-m'n$ implies $m'=n=1$. The only case for 
which the relation $|n-n'|\geq n$ is false is, then, the case $n'=1$, 
so we get $(d,ma+nb)=(a,b)$, which contradicts the hypothesis, so 
Lemma \ref{StructAsc} is proved.
\end{proof}

Lemma \ref{StructAsc} has this important consequence:

\begin{Cor}\label{PropFond} {\bf (characterization of shortest walks)} 
 Let $(a,b)$ be a pair appearing in ${\mathbf{T}}$. 
The shortest way in ${\mathbf{T}}$ from the root to the
pair $(a,b)$ is characterized by the following property:
for any pair $(c,d)$ appearing in this walk, the parent of
$c$ is $|c-d|$.
\end{Cor}

\begin{proof} Let $(c,d)$ be a pair appearing in ${\mathbf{T}}$ which belongs 
to the shortest walk from the root to the pair $(a,b)$. If the parent 
of $c$ is $c+d$ then, by the previous Lemma, either all the ancestors
of $c+d$ are of the form $mc+nd$ with $m$ and $n$ positive integers,
or the pair $(c,d)$ appears among the ancestors of $(c+d,d)$. The
first case is impossible since the walk could not thus start from the pair 
$(1,1)$ which is at the beginning of the tree; the second case is in 
contradiction with the assumption that the walk in consideration is the shortest
from $(1,1)$ to $(a,b)$. So, considering the pair $(c,d)$ appearing in
${\mathbf{T}}$, the parent of $c$ is necessarily $|c-d|$, and the corollary is
proved.
\end{proof}



To conclude the proof of Proposition \ref{ShortestWay}, it is then
enough to verify that the walk  constructed in the
proof of Proposition \ref{Containment} verifies the previous characterization
property. This fact is routinely verified.

\end{proof}



The definition of the random Fibonacci tree implies that whenever we
see two nodes both equal to $1$, the first being the parent of the
second, the successive children which
appear next show the full tree. To avoid repetition in the tree, we will
now focus our attention to the subtree, denoted by ${\mathbf{R}}$, which
avoid redundances.

\subsection{The tree ${\mathbf{R}}$}\label{restricted}

We consider the tree ${\mathbf{R}}$ defined as the subtree of ${\mathbf{T}}$ made of all
shortest walks. In other words, we start from $1$, with only
child $1$. Then, the $(n-1)$ first rows being
constructed, the $n$-th one is made of the nodes $b$ such that,
denoting by $a$ their parent, the pair $(a,b)$ did not already appear
upper in the subtree (that is no row before the $n$-th one shows the 
pair $(a,b)$). The tree ${\mathbf{R}}$ is the
{\em restricted subtree} of ${\mathbf{T}}$. We denote by $r(a,b)$ the value of
the row in which the edge containing $a$ as a parent and $b$ as a child
appears  in the tree ${\mathbf{R}}$.


Lemma \ref{NonAmbigu} ensure that the definition of ${\mathbf{R}}$ 
 is non-ambiguous, at a single exception which is treated 
in Lemma \ref{Zero}.

\begin{Lemme}\label{NonAmbigu}  Any edge $(a,b)$ appearing in ${\mathbf{T}}$ 
appears only 
once in the row $r(a,b)$, apart from 
the pair $(0,1)$ which appears twice in the second and third
rows.


\end{Lemme}

\begin{proof}  The case of the pair  $(0,1)$ is manually treated.
Apart from this case, we know from the characterization of shortest
walks 
that the shortest walk in ${\mathbf{T}}$ from the root to 
the pair $(a,b)$ is such that, for any  pair
$(c,d)$ appearing in this walk, $c$'s parent is
$|d-c|$, so this walk is unique and Lemma \ref{NonAmbigu} is
proved.
\end{proof}

\begin{Lemme}\label{Zero}  The value zero appears only once in
${\mathbf{R}}$ and has no grandchild.
\end{Lemme}

\begin{proof} By Proposition \ref{Containment}, the value $0$ appears
only as a child of $1$, so, by definition of ${\mathbf{R}}$, it cannot
appears twice. Its children in ${\mathbf{T}}$ are $1$ and $1$ (this is the
ambiguity case in the definition of ${\mathbf{R}}$), whose children in
${\mathbf{T}}$ are also $1$ and $1$ and have to be exclude from ${\mathbf{R}}$ since
the pair $(1,1)$ already appears in the root of ${\mathbf{R}}$.
\end{proof}


Lemma \ref{Zero} indicates that the node $0$ of ${\mathbf{R}}$ can be
removed. In the following, this node (and its children) are not
considered as elements of ${\mathbf{R}}$. We will call ${\tilde {\mathbf{R}}}$ the tree
obtained by adding to ${\mathbf{R}}$ the node $0$ corresponding to the left child
of the second $1$. The tree ${\tilde {\mathbf{R}}}$ will be useful to investigate
the positions of the $0$ nodes in ${\mathbf{T}}$ (see section \ref{Zeros}).

Here are the first few rows of ${\mathbf{R}}$. As in the case of ${\mathbf{T}}$, a left
child corresponds to a subtraction and a right child to an addition. 
When a node has only one child, we use a vertical line; Lemma
\ref{GaucheGauche}
will show that such a vertical edge always corresponds to an
addition.

\begin{figure}[H]
{\vskip .5in}
{\hskip 0.9in}\begin{graph}(19,10)(2.5,-0.5)
\newcommand{\node}[4]{%
\textnode #1(#2,#3){#4}[\graphlinecolour{1}]}

\node{Racine}{6.61875}{10}{1}

\node{Fils}{6.61875}{9}{1}

\node{L1n1}{6.61875}{8}{2}

\node{L2n1}{2.455}{7}{1}
\node{L2n2}{10.7825}{7}{3}

\node{L3n1}{2.455}{6}{3}
\node{L3n2}{8.24}{6}{1}
\node{L3n3}{13.325}{6}{5}

\node{L4n1}{0.86}{5}{2}
\node{L4n2}{4.05}{5}{4}
\node{L4n3}{8.24}{5}{4}
\node{L4n4}{11.74}{5}{2}
\node{L4n5}{14.91}{5}{8}


\node{L5n1}{0.86}{4}{5}
\node{L5n2}{3.08}{4}{1}
\node{L5n3}{5.02}{4}{7}
\node{L5n4}{7.24}{4}{3}
\node{L5n5}{9.18}{4}{5}
\node{L5n6}{11.74}{4}{7}
\node{L5n7}{13.92}{4}{3}
\node{L5n8}{15.9}{4}{13}



\node{L6n1}{0.24}{3}{3}
\node{L6n2}{1.48}{3}{7}
\node{L6n3}{3.08}{3}{5}
\node{L6n4}{4.4}{3}{3}
\node{L6n5}{5.64}{3}{11}
\node{L6n6}{7.24}{3}{7}
\node{L6n7}{8.56}{3}{1}
\node{L6n8}{9.8}{3}{9}
\node{L6n9}{11.12}{3}{5}
\node{L6n10}{12.36}{3}{9}
\node{L6n11}{13.92}{3}{11}
\node{L6n12}{15.28}{3}{5}
\node{L6n13}{16.52}{3}{21}





\node{L7n1}{0.24}{2}{8}
\node{L7n2}{1.12}{2}{2}
\node{L7n3}{1.84}{2}{12}
\node{L7n4}{2.72}{2}{4}
\node{L7n5}{3.44}{2}{6}
\node{L7n6}{4.4}{2}{10}
\node{L7n7}{5.28}{2}{4}
\node{L7n8}{6}{2}{18}
\node{L7n9}{6.88}{2}{4}
\node{L7n10}{7.6}{2}{10}
\node{L7n11}{8.56}{2}{6}
\node{L7n12}{9.44}{2}{4}
\node{L7n13}{10.16}{2}{14}
\node{L7n14}{11.12}{2}{12}
\node{L7n15}{12}{2}{2}
\node{L7n16}{12.72}{2}{16}
\node{L7n17}{13.6}{2}{8}
\node{L7n18}{14.32}{2}{14}
\node{L7n19}{15.28}{2}{18}
\node{L7n20}{16.16}{2}{8}
\node{L7n21}{16.88}{2}{34}


\node{L8n1}{0}{1}{5}
\node{L8n2}{0.48}{1}{11}
\node{L8n3}{1.12}{1}{9}
\node{L8n4}{1.6}{1}{5}
\node{L8n5}{2.08}{1}{19}
\node{L8n6}{2.72}{1}{9}
\node{L8n7}{3.2}{1}{1}
\node{L8n8}{3.68}{1}{11}
\node{L8n9}{4.16}{1}{7}
\node{L8n10}{4.64}{1}{13}
\node{L8n11}{5.28}{1}{15}
\node{L8n12}{5.76}{1}{7}
\node{L8n13}{6.24}{1}{29}
\node{L8n14}{6.88}{1}{11}
\node{L8n15}{7.36}{1}{3}
\node{L8n16}{7.84}{1}{17}
\node{L8n17}{8.32}{1}{5}
\node{L8n18}{8.8}{1}{7}
\node{L8n19}{9.44}{1}{13}
\node{L8n20}{9.92}{1}{5}
\node{L8n21}{10.4}{1}{23}
\node{L8n22}{10.88}{1}{7}
\node{L8n23}{11.36}{1}{17}
\node{L8n24}{12}{1}{11}
\node{L8n25}{12.48}{1}{7}
\node{L8n26}{12.96}{1}{25}
\node{L8n27}{13.6}{1}{19}
\node{L8n28}{14.08}{1}{3}
\node{L8n29}{14.56}{1}{25}
\node{L8n30}{15.04}{1}{13}
\node{L8n31}{15.52}{1}{23}
\node{L8n32}{16.16}{1}{29}
\node{L8n33}{16.64}{1}{13}
\node{L8n34}{17.12}{1}{55}





\node{L9n1}{0}{0}{\tiny 13}
\node{L9n2}{0.32}{0}{\tiny 3}
\node{L9n3}{0.64}{0}{\tiny 19}
\node{L9n4}{0.96}{0}{\tiny 7}
\node{L9n5}{1.28}{0}{\tiny 11}
\node{L9n6}{1.6}{0}{\tiny 17}
\node{L9n7}{1.92}{0}{\tiny 7}
\node{L9n8}{2.24}{0}{\tiny 31}
\node{L9n9}{2.56}{0}{\tiny 5}
\node{L9n10}{2.88}{0}{\tiny 13}
\node{L9n11}{3.2}{0}{\tiny 7}
\node{L9n12}{3.52}{0}{\tiny 5}
\node{L9n13}{3.84}{0}{\tiny 17}
\node{L9n14}{4.16}{0}{\tiny 17}
\node{L9n15}{4.48}{0}{\tiny 3}
\node{L9n16}{4.8}{0}{\tiny 23}
\node{L9n17}{5.12}{0}{\tiny 11}
\node{L9n18}{5.44}{0}{\tiny 19}
\node{L9n19}{5.76}{0}{\tiny 25}
\node{L9n20}{6.08}{0}{\tiny 11}
\node{L9n21}{6.4}{0}{\tiny 47}
\node{L9n22}{6.72}{0}{\tiny 7}
\node{L9n23}{7.04}{0}{\tiny 15}
\node{L9n24}{7.36}{0}{\tiny 13}
\node{L9n25}{7.68}{0}{\tiny 7}
\node{L9n26}{8}{0}{\tiny 27}
\node{L9n27}{8.32}{0}{\tiny 11}
\node{L9n28}{8.64}{0}{\tiny 1}
\node{L9n29}{8.96}{0}{\tiny 13}
\node{L9n30}{9.28}{0}{\tiny 9}
\node{L9n31}{9.6}{0}{\tiny 17}
\node{L9n32}{9.92}{0}{\tiny 19}
\node{L9n33}{10.24}{0}{\tiny 9}
\node{L9n34}{10.56}{0}{\tiny 37}
\node{L9n35}{10.88}{0}{\tiny 19}
\node{L9n36}{11.2}{0}{\tiny 5}
\node{L9n37}{11.52}{0}{\tiny 29}
\node{L9n38}{11.84}{0}{\tiny 9}
\node{L9n39}{12.16}{0}{\tiny 13}
\node{L9n40}{12.48}{0}{\tiny 23}
\node{L9n41}{12.8}{0}{\tiny 9}
\node{L9n42}{13.12}{0}{\tiny 41}
\node{L9n43}{13.44}{0}{\tiny 11}
\node{L9n44}{13.76}{0}{\tiny 27}
\node{L9n45}{14.08}{0}{\tiny 17}
\node{L9n46}{14.4}{0}{\tiny 11}
\node{L9n47}{14.72}{0}{\tiny 39}
\node{L9n48}{15.04}{0}{\tiny 31}
\node{L9n49}{15.36}{0}{\tiny 5}
\node{L9n50}{15.68}{0}{\tiny 41}
\node{L9n51}{16}{0}{\tiny 21}
\node{L9n52}{16.32}{0}{\tiny 37}
\node{L9n53}{16.64}{0}{\tiny 47}
\node{L9n54}{16.96}{0}{\tiny 21}
\node{L9n55}{17.28}{0}{\tiny 89}


\node{rho1}{-1}{9.5}{$\rho_{1}$}
\node{rho1Bis}{18}{9.5}{}
\edge{rho1}{rho1Bis}[\graphlinedash{3 3}]
\node{rho2}{-1}{8.5}{$\rho_{2}$}
\node{rho2Bis}{18}{8.5}{}
\edge{rho2}{rho2Bis}[\graphlinedash{3 3}]
\node{rho3}{-1}{7.5}{$\rho_{3}$}
\node{rho3Bis}{18}{7.5}{}
\edge{rho3}{rho3Bis}[\graphlinedash{3 3}]
\node{rho4}{-1}{6.5}{$\rho_{4}$}
\node{rho4Bis}{18}{6.5}{}
\edge{rho4}{rho4Bis}[\graphlinedash{3 3}]
\node{rho5}{-1}{5.5}{$\rho_{5}$}
\node{rho5Bis}{18}{5.5}{}
\edge{rho5}{rho5Bis}[\graphlinedash{3 3}]
\node{rho6}{-1}{4.5}{$\rho_{6}$}
\node{rho6Bis}{18}{4.5}{}
\edge{rho6}{rho6Bis}[\graphlinedash{3 3}]
\node{rho7}{-1}{3.5}{$\rho_{7}$}
\node{rho7Bis}{18}{3.5}{}
\edge{rho7}{rho7Bis}[\graphlinedash{3 3}]
\node{rho8}{-1}{2.5}{$\rho_{8}$}
\node{rho8Bis}{18}{2.5}{}
\edge{rho8}{rho8Bis}[\graphlinedash{3 3}]
\node{rho9}{-1}{1.5}{$\rho_{9}$}
\node{rho9Bis}{18}{1.5}{}
\edge{rho9}{rho9Bis}[\graphlinedash{3 3}]
\node{rho10}{-1}{0.5}{$\rho_{10}$}
\node{rho10Bis}{18}{0.5}{}
\edge{rho10}{rho10Bis}[\graphlinedash{3 3}]



\edge{Racine}{Fils}

\edge{Fils}{L1n1}

\edge{L1n1}{L2n1}
\edge{L1n1}{L2n2}

\edge{L2n1}{L3n1}
\edge{L2n2}{L3n2}
\edge{L2n2}{L3n3}

\edge{L3n1}{L4n1}
\edge{L3n1}{L4n2}
\edge{L3n2}{L4n3}
\edge{L3n3}{L4n4}
\edge{L3n3}{L4n5}

\edge{L4n1}{L5n1}
\edge{L4n2}{L5n2}
\edge{L4n2}{L5n3}
\edge{L4n3}{L5n4}
\edge{L4n3}{L5n5}
\edge{L4n4}{L5n6}
\edge{L4n5}{L5n7}
\edge{L4n5}{L5n8}


\edge{L5n1}{L6n1}
\edge{L5n1}{L6n2}
\edge{L5n2}{L6n3}
\edge{L5n3}{L6n4}
\edge{L5n3}{L6n5}
\edge{L5n4}{L6n6}
\edge{L5n5}{L6n7}
\edge{L5n5}{L6n8}
\edge{L5n6}{L6n9}
\edge{L5n6}{L6n10}
\edge{L5n7}{L6n11}
\edge{L5n8}{L6n12}
\edge{L5n8}{L6n13}


\edge{L6n1}{L7n1}
\edge{L6n2}{L7n2}
\edge{L6n2}{L7n3}
\edge{L6n3}{L7n4}
\edge{L6n3}{L7n5}
\edge{L6n4}{L7n6}
\edge{L6n5}{L7n7}
\edge{L6n5}{L7n8}
\edge{L6n6}{L7n9}
\edge{L6n6}{L7n10}
\edge{L6n7}{L7n11}
\edge{L6n8}{L7n12}
\edge{L6n8}{L7n13}
\edge{L6n9}{L7n14}
\edge{L6n10}{L7n15}
\edge{L6n10}{L7n16}
\edge{L6n11}{L7n17}
\edge{L6n11}{L7n18}
\edge{L6n12}{L7n19}
\edge{L6n13}{L7n20}
\edge{L6n13}{L7n21}



\edge{L7n1}{L8n1}
\edge{L7n1}{L8n2}
\edge{L7n2}{L8n3}
\edge{L7n3}{L8n4}
\edge{L7n3}{L8n5}
\edge{L7n4}{L8n6}
\edge{L7n5}{L8n7}
\edge{L7n5}{L8n8}
\edge{L7n6}{L8n9}
\edge{L7n6}{L8n10}
\edge{L7n7}{L8n11}
\edge{L7n8}{L8n12}
\edge{L7n8}{L8n13}
\edge{L7n9}{L8n14}
\edge{L7n10}{L8n15}
\edge{L7n10}{L8n16}
\edge{L7n11}{L8n17}
\edge{L7n11}{L8n18}
\edge{L7n12}{L8n19}
\edge{L7n13}{L8n20}
\edge{L7n13}{L8n21}
\edge{L7n14}{L8n22}
\edge{L7n14}{L8n23}
\edge{L7n15}{L8n24}
\edge{L7n16}{L8n25}
\edge{L7n16}{L8n26}
\edge{L7n17}{L8n27}
\edge{L7n18}{L8n28}
\edge{L7n18}{L8n29}
\edge{L7n19}{L8n30}
\edge{L7n19}{L8n31}
\edge{L7n20}{L8n32}
\edge{L7n21}{L8n33}
\edge{L7n21}{L8n34}


\edge{L8n1}{L9n1}
\edge{L8n2}{L9n2}
\edge{L8n2}{L9n3}
\edge{L8n3}{L9n4}
\edge{L8n3}{L9n5}
\edge{L8n4}{L9n6}
\edge{L8n5}{L9n7}
\edge{L8n5}{L9n8}
\edge{L8n6}{L9n9}
\edge{L8n6}{L9n10}
\edge{L8n7}{L9n11}
\edge{L8n8}{L9n12}
\edge{L8n8}{L9n13}
\edge{L8n9}{L9n14}
\edge{L8n10}{L9n15}
\edge{L8n10}{L9n16}
\edge{L8n11}{L9n17}
\edge{L8n11}{L9n18}
\edge{L8n12}{L9n19}
\edge{L8n13}{L9n20}
\edge{L8n13}{L9n21}
\edge{L8n14}{L9n22}
\edge{L8n14}{L9n23}
\edge{L8n15}{L9n24}
\edge{L8n16}{L9n25}
\edge{L8n16}{L9n26}
\edge{L8n17}{L9n27}
\edge{L8n18}{L9n28}
\edge{L8n18}{L9n29}
\edge{L8n19}{L9n30}
\edge{L8n19}{L9n31}
\edge{L8n20}{L9n32}
\edge{L8n21}{L9n33}
\edge{L8n21}{L9n34}
\edge{L8n22}{L9n35}
\edge{L8n23}{L9n36}
\edge{L8n23}{L9n37}
\edge{L8n24}{L9n38}
\edge{L8n24}{L9n39}
\edge{L8n25}{L9n40}
\edge{L8n26}{L9n41}
\edge{L8n26}{L9n42}
\edge{L8n27}{L9n43}
\edge{L8n27}{L9n44}
\edge{L8n28}{L9n45}
\edge{L8n29}{L9n46}
\edge{L8n29}{L9n47}
\edge{L8n30}{L9n48}
\edge{L8n31}{L9n49}
\edge{L8n31}{L9n50}
\edge{L8n32}{L9n51}
\edge{L8n32}{L9n52}
\edge{L8n33}{L9n53}
\edge{L8n34}{L9n54}
\edge{L8n34}{L9n55}


\end{graph}


\caption{The restricted tree ${\mathbf{R}}={\mathbf{R}}_{(1,1)}$ }

\end{figure}


Let us remark, again without further elaboration, that 
the sequence of labels in the tree ${\mathbf{R}}$, read in
breadth-first order ($1$, $1$, $2$, $1$, $3$, $3$, $1$, $5$, $2$,
$4$, $4$, $2$, $8$\ldots) is a {\em $\beta$-regular
sequence}, as defined by  Allouche, Scheicher and
Tichy \cite{AST},
where here $\beta$ is the numeration
system defined by the Fibonacci sequence.



\begin{Notation}  Let $a$ be a node of ${\mathbf{R}}$. If $a$ has a left
(resp. right) child, it is denoted by $c^-(a)$ (resp. $c^+(a)$).
\end{Notation}



\begin{Lemme}\label{GaucheGauche}  In ${\mathbf{R}}$, if $b$ is the left 
child of $a$, then $b$ has no left child.

\end{Lemme}

\begin{proof} Let assume that we can find three nodes $x$, 
$y$ and $z$ such that
$z=c^-(y)$ and $y=c^-(x)$. By considering
successive parents if necessary, we can suppose that
$x=c^+(w)$.

Let $v$ be the parent of $w$. Then, we have
$x=v+w$, so $y=|x-w|=v$ and
$z=|y-x|=|v-(v+w)|=w$, so
$(y,z)=(v,w)$, which contradicts the
non-redundance in the definition of ${\mathbf{R}}$.
\end{proof}

\begin{Lemme}\label{Ordre}  In ${\mathbf{R}}$, if $a$ has $b$ as 
a right (resp.
left) child, then $b$ is  smaller (resp.  
bigger) than $a$. The only case of equality corresponds to the
pair $(1,1)$ in the beginning of the tree.
\end{Lemme}

\begin{proof} Let us denote by $z$ the parent of $a$. 
If $b=c^+(a)$, then it is obvious that
$b&gt;a$ since, apart for nodes in the top of the tree, we
have $b=a+z$ and $z&gt; 0$ by Lemma \ref{Zero}
(and the exclusion of the $0$-node we made after this lemma).

If $b=c^-(a)$, then (if $a$ is not the root of ${\mathbf{R}}$), 
by Lemma \ref{GaucheGauche} 
we have $a=c^+(z)$ so, by the beginning of the proof,
$a&gt;z$, so $b=a-z&lt;a$, and the proof is
complete.
\end{proof}

\begin{Lemme}\label{Droit}  In ${\mathbf{R}}$, every node has a right child.
\end{Lemme}

\begin{proof} Let us consider the node $b$, which parent is
$a$. In ${\mathbf{T}}$, the right child of $b$ is $a+b$. It
remains to show that the shortest walk in ${\mathbf{T}}$ from the root to
$(b,a+b)$ is such that $b$ has $a$ as parent.
But this is a simple consequence of the characteristic property of 
shortest walks (Corollary \ref{PropFond}): 
the parent of $b$ is $|(a+b)-b| =
a$.

\end{proof}

\begin{Lemme}\label{UnPuisDeux}  In ${\mathbf{R}}$, 
if the node $a$ has $b$ as only  child,
then $b$ has two children.
\end{Lemme}

\begin{proof} By Lemma \ref{Droit}, $b=c^+(a)$. By Lemma
\ref{Droit} again, $b$ has a right child, which is $a+b$.
In ${\mathbf{T}}$, the left child of $b$ is $|a-b|$, which is
equal to $b-a$ by Lemma \ref{Ordre}. Again by the
characteristic property of shortest walks, the parent of $b$ in
the shortest walk to $(b,b-a)$ is
$|b-(b-a)|=a$, and we are done.
\end{proof}

\begin{Lemme}\label{DroiteDeux}  In ${\mathbf{R}}$, if 
the node $b$ is a right child, then it has two children.
\end{Lemme}

The proof goes as in Lemma \ref{UnPuisDeux}.


\begin{Notation}  The set of edges from the $(n-1)$-th to the 
$n$-th row of ${\mathbf{R}}$ is denoted by $\rho_{n}$
(by convention, the root defines the $0$-th row, so 
the edge from the root $1$ to its only child $1$ 
corresponds to $\rho_{1}$, the next one from $1$ to $2$ coresponds to
$\rho_{2}$, and so on). In $\rho_{n}$, the subset of left (resp. right) 
edges  is denoted by $\rho^-_{n}$ (resp.
$\rho^+(n)$). A set $X$ of edges in ${\mathbf{R}}$ being given, we denote by
$c(X)$, $c^-(X)$ and $c^{+}(X)$ respectively the set of children, left
children and right children of $X$ in ${\mathbf{R}}$. We also denote by
$S(X)$ the sum of the values of all the final nodes of $X$.

We denote by $(F_{n})_{n}$ the classical Fibonacci sequence:
$F_{0}=0$, $F_{1}=1$ and, for all $n\geq 2$, $F_{n}=F_{n-1}+F_{n-2}$.


\end{Notation}

We can now give two quite unexpected properties of ${\mathbf{R}}$.


\begin{Prop}\label{Fib}  For all $n\geq 2$, we have

\[\Card(\rho^-_{n})=F_{n-2}\qquad\mbox{and}\qquad
\Card(\rho^+_{n})=F_{n-1},\]
\noindent and so
\[\Card(\rho_{n})=F_{n}.\]
\end{Prop}

\begin{proof} The property is easily verified for the first rows. 
Let assume that the property is true for all
rows until the $(n-1)$-th one. By Lemma \ref{Droit}, we have
$\Card(\rho_{n-1})=\Card(c^+(\rho_{n-1}))=\Card(\rho^+_{n})$, so
$\Card(\rho^+_{n})=F_{n-1}$. By Lemmas \ref{UnPuisDeux} and 
\ref{DroiteDeux}, we have
$\Card(\rho^-_{n})=\Card(\rho^+_{n-1})=\Card(\rho_{n-2})=F_{n-2}$, so 
we are done.
\end{proof}


\begin{Prop}\label{SumEss}  Let us define  $G_{n}$ as $S(\rho_{n})$ for
all $n\geq 1$.
One has $G_{1}=1$,
$G_{2}=2$, $G_{3}=4$ and, for any $n&gt;3$, $G_{n}=2G_{n-1}+G_{n-3}$.
\end{Prop}

\begin{proof} We write $G^-_{n}$ (resp. $G^+_{n}$) for
$S(\rho^-_{n})$ (resp. $S(\rho^+_{n})$). Lemmas \ref{GaucheGauche},
\ref{Ordre} and \ref{DroiteDeux} imply the relation
$G^-_{n}=G^+_{n-1}-G_{n-2}$. We split the edges of $\rho_{n}^+$ in two
subsets: the one, say $\sigma^+_{n}$, is composed by 
the edges which are children
of elements of $\rho^+_{n-1}$, the other, $\sigma^-_{n}$, is composed by 
the edges which are children
of elements of $\rho^-_{n-1}$. Lemma \ref{Droit} implies that
$S(\sigma^+_n)=G^+_{n-1}+G_{n-2}$, Lemmas \ref{GaucheGauche} and
\ref{DroiteDeux} that $S(\sigma^-_{n})=G^-_{n-1}+G^+_{n-2}$. Thus, we 
get
\begin{eqnarray*}
G_{n}=G^-_{n}+G^+_{n}&amp;=&amp;G^-_{n}+S(\sigma^-_{n})+S(\sigma^+_{n})\\
&amp;=&amp;(G^+_{n-1}-G_{n-2})+(G^-_{n-1}+G^+_{n-2})+(G^+_{n-1}+G_{n-2})\\
&amp;=&amp;2G^+_{n-1}+G^-_{n-1}+G^+_{n-2}\\
&amp;=&amp;2G_{n-1}+G^+_{n-2}-G^-_{n-1}\\
&amp;=&amp;2G_{n-1}+G_{n-3},
\end{eqnarray*}
the relation $G^+_{n-2}-G^-_{n-1}=G_{n-3}$ coming from Lemmas
\ref{GaucheGauche}, \ref{Ordre}, \ref{Droit} and \ref{DroiteDeux}.
\end{proof}

The same kind of study shows that, more generally,   
if we write 
$v_{n}=\alpha_{n}a+\beta_{n}b$ for 
the sum of the $n$-th row of the general restricted 
tree, then 
we have
\[\alpha_{0}=1\quad
\alpha_{1}=0\quad\alpha_{2}=1\quad\alpha_{3}=2
\quad\alpha_{n}=2\alpha_{n-1}+\alpha_{n-3}\mbox
{ for $n\geq 4$ (so $\alpha_{n}=G_{n-1}$),}\]
\[\beta_{0}=0\quad\beta_{1}=1\quad\beta_{2}=1\quad\beta_{3}=2\quad 
\beta_{n}=2\beta_{n-1}+\beta_{n-3} 
\mbox{ for $n\geq 3$}.\]




\begin{Cor}\label{CroissRest}  Let us denote by ${\tilde m}_{n}$ 
the average value of an element of the $n$-th row of ${\mathbf{R}}$. As $n$ goes 
to infinity, the ratio
${\tilde m}_{n+1}/{\tilde m}_{n}$ tends to
$\alpha/\varphi\approx 1.363117$, where
$\alpha$ is the only real zero of the equation $x^3=2x^2+1$ and
$\varphi$ the golden ratio.
\end{Cor}

\begin{proof} Classical facts about linear recurring sequences
show that the ratio $G_{n+1}/G_{n}$ tends to $\alpha$ as $n$ tends to
infinity. Since Proposition \ref{Fib} shows that ${\tilde
m}_{n}=G_{n}/F_{n}$, we get ${\tilde m}_{n+1}/{\tilde
m}_{n}=(G_{n+1}/G_{n})\cdot(F_{n+1}/F_{n})$ and the result follows
from the fact that $F_{n+1}/F_{n}$ tends to $\varphi$ as $n$ goes to
infinity.
\end{proof}







\subsection{Projection of walks of ${\mathbf{T}}$ into walks of ${\mathbf{R}}$}\label{TR}

A (finite) walk in ${\mathbf{T}}$ can be represented as a finite sequence 
$(w_{i})_{0\leq i\leq N}$ of $+$ and $-$ signs. To such a sequence
is associated the random Fibonacci sequence $(g_{n})_{n}$ defined by
$g_{0}=g_{1}=1$ and, for all $n\geq 2$, $g_{n}=g_{n-1}+g_{n-2}$ iff
$w_{n-2}=+$. A finite walk $(w_{i})_{0\leq i\leq N}$ being 
given, we generically denote by
$(g_{i})_{0\leq i\leq N}$ the associated random Fibonacci sequence,
that is the values of the nodes successively
attained in ${\mathbf{T}}$ by this walk. 





The following proposition gives a way to 
transform  a walk in ${\mathbf{T}}$ into a walk on ${\mathbf{R}}$.






\begin{Lemme}\label{Remontee}  For $N\geq 2$, 
let $(w_{n})_{0\leq n\leq N}$ be a finite
walk in ${\mathbf{T}}$  such that a minus sign is never followed by another minus 
sign, apart for $w_{N-1}$ and $w_{N}$ (both minus signs). Denoting by
$(g_{i})_{0\leq i\leq N+2}$ the corresponding node sequence, we have 
$(g_{N+2},g_{N+1}) = (g_{N-1},g_{N})$.


\end{Lemme}

\begin{proof} The assumption made on $(w_{i})_{0\leq i&lt;N}$,
together with Lemmas \ref{GaucheGauche}, \ref{Droit} and
\ref{DroiteDeux} imply that the walk $(w_{i})_{0\leq i&lt;N}$ is a walk
in ${\mathbf{R}}$ as well as a walk in ${\mathbf{T}}$.
By Lemma \ref{Ordre}, we thus have
$g_{N+1}&lt;g_{N}$, so $g_{N+2}=g_{N}-g_{N+1}$. 
By the characterization of shortest walks (Corollary \ref{PropFond}), 
we have also $g_{N-1}=g_{N}-g_{N+1}$ (so
$g_{N-1}=g_{N+2}$) and
$g_{N-2}=|g_{N-1}-g_{N}|=g_{N+1}$, so we are
done.
\end{proof}

The previous lemma means that the left child in ${\mathbf{T}}$ of a left 
child $b$ in ${\mathbf{R}}$ can simply be seen as $b$'s grandparent. For certain 
walks in ${\mathbf{T}}$, it is thus possible to define a corresponding walk in
${\mathbf{R}}$, obtained by cutting every succession of $+--$ (note that such a
cut may make another $+--$ appear to be itself removed, and so on).
For example, the walk $+-++----$ in ${\mathbf{T}}$ gives the walk $+-$ in ${\mathbf{R}}$.

The walks in ${\mathbf{T}}$ for which some attained nodes have the value $0$ do
not correspond to a walk in ${\mathbf{R}}$, since ${\mathbf{R}}$ do not contain any node
equal to $0$. Conversely, to any walk in ${\mathbf{T}}$ for which $a_{i}\neq 0$ 
for all $i$ corresponds a walk in ${\mathbf{R}}$. 
(To be able to project any walk in ${\mathbf{T}}$ into a walk in a non-redundant
tree, it would be possible to consider ${\tilde {\mathbf{R}}}$ instead of
${\mathbf{R}}$.)



\section{Proof of Theorem \ref{Main1}}


In the following, ${\mathbf{R}}$ is considered as a subset of ${\mathbf{T}}$.



\begin{Notation}  For any subset $X$ of edges of ${\mathbf{T}}$, we denote by
$s(X)$ (for {\em successor}) the set of all edges which are children 
of elements of $X$ in
${\mathbf{T}}$. If $X$ and $Y$ are two
subsets of ${\mathbf{T}}$ (non necessarily disjoint), we write $X+Y$ for the
disjoint union of $X$ and $Y$. The disjoint union $X+X$ is written as 
$2X$ and, more generally, $mX$ stands for the union of $m$ disjoint
copies of $X$. In the following, we will identify 
the set $mX$ with the set obtained by multiplying each element
of $X$ by $m$ (that is: for the edge $e$ limited by the nodes $a$ and $b$,
$2e$ can be seen as the edge limited by $2a$ and $2b$); 
this interpretation of $mX$  allows us to extend the
notation to $zX$, where $z$ is any real number.


Recalling that $\rho_{n}$ denotes the $n$-th row of edges of ${\mathbf{R}}$, we denote by 
$\rho_{n}^{(a,b)}$ the $n$-th row of edges of ${\mathbf{R}}_{(a,b)}$, 
$\tau_{n}$  the $n$-th row of edges of ${\mathbf{T}}$ and $\tau_{n}^{(a,b)}$ the $n$-th
row of edges of ${\mathbf{T}}_{(a,b)}$.

\end{Notation}


The proof of Theorem \ref{Main1} runs as follow:

\begin{itemize}

\item Step 1: show that the growth rate of $\rho_{n}^{(a,b)}$ is the
same for any pair $(a,b)$ such that $ab\neq 0$;

\item Step 2: give an explicit expression of $\tau_{n}^{(a,b)}$ in
terms of $\rho_{k}^{(|b-a|,a)}$ (with $k\leq n$) in the cases
$(a,b)=(1,\varphi)$ and $(a,b)=(1,\varphi^{-1})$ (with a slight abuse 
of notation which will be explained soon) (recall that
$\varphi=(1+\sqrt{5})/2$);

\item Step 3: deduce from step 2 the explicit growth rate of the
sequences $(S(\tau_{n}^{(a,b)}))_{n}$ for the two 
pairs $(1,\varphi)$ and $(1,\varphi^{-1})$ (we find  the same growth
rates in the two cases);

\item Step 4: deduce from the linearity  of the function
$(a,b)\longmapsto (\tau_{n}^{(a,b)})_{n}$ that the 
growth rate found in step 3 is also the growth rate of the sequence
$(S(\tau_{n}^{(a,b)}))_{n}$ for any pair $(a,b)$.

\end{itemize}

The growth rate found in step 4 will correspond to the value
$\alpha-1$ mentioned in the statement of Theorem \ref{Main1}, so step 
4 will conclude the proof.

\subsection{Step 1: the growth rate of $\rho_{n}^{(a,b)}$ does not
depend on $(a,b)$}

It is a simple consequence of the remark made after the 
proof of Proposition \ref{SumEss}:  since, for any pair 
$(a,b)$, the sequence $(S(\rho_{n}^{(a,b))})_{n}$ is a linear
combination of two linear recurring
sequences both defined by their three first terms and the recurrence property 
$u_{n+1}=2u_{n}+u_{n-2}$, the growth rate of this sequence is the same
for all pairs $(a,b)$ (with $ab\neq 0$), and this growth rate is
$\alpha$, the only real zero bigger than $1$ of the equation
$x^3=2x^2+1$.

\subsection{Step 2: an explicit expression of $\tau_{n}^{(a,b)}$ in
terms of $\rho_{k}^{(|b-a|,a)}$ for $(a,b)=(1,\varphi)$ or
$(1,\varphi^{-1})$}

Let us explain first the slight abuse of notation: in the case
$b=\varphi^{-1}$, the tree ${\mathbf{R}}_{(|b-a|,a)}$ is not a subtree of
${\mathbf{T}}_{(a,b)}$ (even after removing its root), since the child of the node
$a$ in ${\mathbf{R}}_{(|b-a|,a)}$ is not $b=\varphi^{-1}$ but $1+\varphi^{-2}$.
Since the recurring properties of restricted trees do not depend on
the value of their root, this abuse of notation is of no consequence,
and we'll keep it for simplicity.

In the following, we sometimes write $\tau_{n}$ and $\rho_{n}$ instead of
$\tau_{n}^{(a,b)}$ and $\rho_{n}^{(|b-a|,a)}$, the context fixing 
either that the assertions are true for all pairs $(a,b)$ or only for some 
explicit pairs $(a,b)$.

Lemma \ref{Remontee} has the following easy an useful consequence:

\begin{Lemme}\label{SuccR}  For all $n &gt; 3$, we have
$s(\rho_{n})=\rho_{n+1}+\rho_{n-2}$.
\end{Lemme}



Let us consider now the beginning of the trees ${\mathbf{T}}_{(1,\varphi)}$ and
${\mathbf{T}}_{(1,\varphi^{-1})}$ (where $\rho_{2}=\rho_{2}^{(\varphi^{-1},1)}$
for the left figure and $\rho_{2}=\rho_{2}^{(\varphi^{-2},1)}$ for the
right one, with the previous abuse of notation in this latter case).


\begin{figure}[H]
{\hskip 1.2in}
\begin{graph}(19,7)(5,3)
\newcommand{\node}[4]{%
\textnode #1(#2,#3){#4}[\graphlinecolour{1}]}

\node{Rac}{5}{8}{$1$}

\node{FilsRac}{5}{7}{$\varphi$}

\node{PetitFils1}{3}{6}{$\varphi^{-1}$}
\node{PetitFils2}{7}{6}{$\varphi^{2}$}

\node{L2n1}{2}{4}{$1$}
\node{L2n2}{4}{4}{$\varphi+\varphi^{-1}$}
\node{L2n3}{6}{4}{$1$}
\node{L2n4}{8}{4}{$\varphi^3$}


\edge{Rac}{FilsRac}

\edge{FilsRac}{PetitFils1}
\edge{FilsRac}{PetitFils2}

\edge{PetitFils1}{L2n1}[\graphlinedash{3 3}]
\edge{PetitFils1}{L2n2}
\edge{PetitFils2}{L2n3}
\edge{PetitFils2}{L2n4}

\edgetext{Rac}{FilsRac}{$\rho_{2}$}
\edgetext{PetitFils1}{L2n1}{$\varphi^{-1}\rho_{2}$}


%2

\node{2Rac}{15}{8}{$1$}

\node{2FilsRac}{15}{7}{$\varphi^{-1}$}

\node{2PetitFils1}{13}{6}{$\varphi^{-2}$}
\node{2PetitFils2}{17}{6}{$\varphi$}

\node{2L2n1}{12}{4}{$\varphi^{-3}$}
\node{2L2n2}{14}{4}{$1$}
\node{2L2n3}{16}{4}{$1$}
\node{2L2n4}{18}{4}{$\varphi+\varphi^{-1}$}


\edge{2Rac}{2FilsRac}

\edge{2FilsRac}{2PetitFils1}
\edge{2FilsRac}{2PetitFils2}

\edge{2PetitFils1}{2L2n1}[\graphlinedash{3 3}]
\edge{2PetitFils1}{2L2n2}
\edge{2PetitFils2}{2L2n3}
\edge{2PetitFils2}{2L2n4}

\edgetext{2Rac}{2FilsRac}{$\rho_{2}$}
\edgetext{2PetitFils1}{2L2n1}{$\varphi^{-2}\rho_{2}$}





\end{graph}

\caption{The trees ${\mathbf{T}}_{(1,\varphi)}$ and ${\mathbf{T}}_{(1,\varphi^{-1})}$.}
\end{figure}

We're interested in the sequence $s^n(\rho_{2}^{(|b-a|,a)})$ for
$(a,b)=(1,\varphi)$ and $(1,\varphi^{-1})$. Let us define $z$ as
$z:=|b-a|$: we thus have $z=\varphi^{-1}$ for $b=\varphi$ and
$z=\varphi^{-2}$ for $b=\varphi^{-1}$. Together with 
the rules given in Lemma \ref{SuccR}, we have the following
rules for $b=\varphi$ or $\varphi^{-1}$:

\[s(\rho_{2}^{(z,1)})=\rho_{3}^{(z,1)},\]

\[s(\rho_{3}^{(z,1)})=\rho_{4}^{(z,1)}+
z\rho_{2}^{(z,1)}.\]


Let us define, for all integer $m\geq 2$
\[\nu_{m}:=\sum_{i=0}^{\lfloor m/2\rfloor -1}z^{i}\rho_{m-2i}.\]

\begin{Lemme}\label{SuccNu} For $(a,b):=(1,\varphi)$ or
$(1,\varphi^{-1})$, we have $s(\nu_{2})=\nu_{3}$,
$s(\nu_{3})=\nu_{4}$ and, for all $m\geq 4$:

\[s(\nu_{m})=\nu_{m+1}+\nu_{m-2}.\]

\end{Lemme}


\begin{proof} It is a simple application of Lemma \ref{SuccR} and
the previous rules for $s(\rho_{2})$ and $s(\rho_{3})$.
\end{proof}


We then get the desired link between the rows of ${\mathbf{R}}_{(|b-1|,1)}$ and 
${\mathbf{T}}_{(1,b)}$ for $b=\varphi$ or $\varphi^{-1}$. 

\begin{Prop}\label{LienRT}  For all $n\geq 0$ and
$(a,b)=(1,\varphi)$ or $(1,\varphi^{-1})$ we have:
\[\tau_{n+2}=s^n(\rho_{2})=\sum_{m=0}^{\lfloor n/3\rfloor}\left({n\choose m}-
2{n \choose m-1}\right) \nu_{n+2-3m}.\]
\end{Prop}

Before proving it, let us give the following combinatorial interpretation
of this proposition: the
set $\nu_{n+2-3m}$ is the set of nodes attained by walks of length $n$
in the random Fibonacci tree such that the projection of such a walk in the
restricted tree is obtained by the cut of $m$ sequences $+--$. The
value ${n\choose m}-2{n \choose m-1}$ corresponds to the number of
such walks leading to 
all nodes whose projection  in 
the restricted tree (see subsection \ref{TR}) are equal to a fixed
node.

\begin{proof} We write $c_{n,m}$ for 
${n\choose m}-2{n \choose m-1}$: a classical relation in Pascal's
triangle shows that 
$c_{n,m}+c_{n,m+1}=c_{n+1,m+1}$ for any $n$ and $m$.

The desired property is easily 
verified for the first values of $n$. 
Let assume for example that the property is true until $n=3k$ where $k$ is a 
positive integer. Thus, by Lemma \ref{SuccNu}, and the induction
hypothesis, we get
\begin{eqnarray*}
\tau_{n+3}&amp;=&amp;s(s^{n}(\rho_{2}))\\
&amp;=&amp;s\left(\sum_{m=0}^{k}c_{n,m} 
\nu_{n+2-3m}\right)\\
&amp;=&amp;s( c_{n,k} \nu_{2} )+ \sum_{m=0}^{k-1} c_{n,m}
\cdot(\nu_{n-3(m-1)}+\nu_{n-3m})\\
&amp;=&amp;c_{n,k}\nu_{3}+c_{n,0}\nu_{n+3}+c_{n,k-1}\nu_{n-3(k-1)}+
\sum_{m=0}^{k-2}(c_{n,m+1}+c_{n,m})\nu_{n-3m}\\
&amp;=&amp;(c_{n,k}+c_{n,k-1})\nu_{3}+\sum_{m=-1}^{k-2}(c_{n,m+1}+c_{n,m})\nu_{n-3m}\\
&amp;=&amp;c_{n+1,k}\nu_{3}+
\sum_{m=-1}^{k-2}c_{n+1,m+1}\nu_{n-3m}\\
&amp;=&amp;\sum_{m=0}^kc_{n+1,m}\nu_{(n+1)+2-3m}.
\end{eqnarray*}

The same calculation works when $n=3k+1$. 
When $n=3k+2$, it also works, with the use of the
complementary fact, routinely proved, that for any integer $N$, the
equality $c_{3N,N}=c_{3N-1,N-1}$ holds (one has to apply then this
equality to $N=k+1$). (To be fully convinced, the reader is 
strongly encouraged to
write the first $\tau_{n}$s in terms of $\rho_{i}$s with the help of
Lemma \ref{LienRT} and arrange these terms in a convenient way to
show the $\nu_{i}$s.)
\end{proof}


It is interesting to remark that, as a simple calculation shows, 
the set $[1,\lfloor n/3\rfloor]$ in which $i$ 
varies in the formula given in Proposition \ref{LienRT} is exactly the
set of integers $i$ for which the quantity ${n\choose i}-
2{n \choose i-1}$ is positive. The following proof of
Theorem \ref{Main1} seems to us not as elegant as Proposition
\ref{LienRT}, and we should expect a less technical way to conclude - 
a way that, at now, we failed to found.

\subsection{Step 3: an explicit expression of the growth rate of
$S(\tau_{n}^{(1,\varphi)})$ and $S(\tau_{n}^{(1,\varphi^{-1})})$}


We know by elementary theory of linear recurring sequences that any
sequence $(u_{n})_{n}$ such that $u_{n}=2u_{n-1}+u_{n-3}$ for all $n$ 
verifies that there exists $\mu\in\R$ and $\nu\in\C$ depending only on 
the three first terms of $(u_{n})_{n}$ and such that, for any $n$:
\[u_{n}=\mu\alpha^n+\nu\beta^n+\overline{\nu}\overline{\beta}^n,\]
\noindent where $\alpha$ is the real zero of the equation
$x^3=2x^2+1$ and $\beta$ and $\overline{\beta}$ the complex ones. A
calculation shows that $\alpha\approx 2.2055694$ and that 
$\beta\approx -0.1027847+0.6654569i$. Thus, the part 
$\nu\beta^n+\overline{\nu}\overline{\beta}^n$ in the expression of
$u_{n}$ goes exponentially fast to zero. More precisely we have, up to
a multiplicative constant, the estimation $|\nu\beta^n+
\overline{\nu}\overline{\beta}^n|\leq |\beta|^n\approx 0.673348^n$.

The definition of $\nu_{n}$ given before Lemma \ref{SuccNu} leads,
then, to an expression of $S(\nu_{n})$ composed of 
three parts, all of them being obtained by 
replacing in the right side of the equality all $\rho_{k}$s by
$\alpha^k$, $\beta^k$ or $\overline{\beta}^k$ and introduce the
multiplicative constant $\mu$, $\nu$ or $\overline{\nu}$. Our first
goal is to prove that the parts with $\beta$ and $\overline{\beta}$
can be removed from the study. For any number $x$, we have, by an
elementary calculation:


\[\sigma_{m}(x):=\sum_{i=0}^{\lfloor m/2\rfloor -1}
z^{i}x^{m-2i}=x^m\cdot\frac{1-(z
x^{-2})^{\lfloor m/2\rfloor}}{1-z x^{-2}}.\]


This sequence is, roughly speaking, exponential with ratio $x$ when
$|zx^{-2}|&lt;1$ and exponential 
with ratio $z^{1/2}$ if $|zx^{-2}|&gt;1$ 
(it is not exactly true in the latter case, where we should
take into account the presence of a complementary factor
$x^{m-2\lfloor m/2\rfloor}$; the
reader can ensure that this abuse is not important, since the cases
for which it occurs will leave to negligible sequences in what
follows).


Let us now define the following sequence:
\[\Sigma_{n}(x):=\sum_{m=0}^{\lfloor n/3\rfloor}c_{n,m}\sigma_{n+2-3m}(x).\]


We can then write, up to a multiplicative constant for each term in
the right side of the equality:
\[S(\tau_{n+2})=\Sigma_{n}(\alpha)+
\Sigma_{n}(\beta)+\Sigma_{n}(\overline{\beta}).\]

For any $x$ we have
\begin{eqnarray*}
\lefteqn{(1-zx^{-2})\Sigma_{n}(x)}\\
&amp;=&amp;\sum_{m=0}^{\lfloor n/3\rfloor}c_{n,m}\cdot x^{n+2-3m}\cdot
(1-(zx^{-2})^{\lfloor(n+2-3m)/2\rfloor})\\
&amp;=&amp; \left(\sum_{m=0}^{\lfloor n/3\rfloor}c_{n,m}x^{n+2-3m}\right)-
\left(\sum_{m=0}^{\lfloor
n/3\rfloor}c_{n,m}x^{n+2-3m-2\lfloor(n+2-3m)/2\rfloor}
z^{\lfloor(n+2-3m)/2\rfloor}\right).
\end{eqnarray*}

We denote by $Z_{n}(x)$ the first sum in the right side, and by
$Z'_{n}(x)$ the second one.





Since $|z|&lt;1$, for any $x\geq 0$ we have
\[Z'_{n}(x)\leq  x
\sum_{m=0}^{\lfloor n/3\rfloor} c_{n,m}
\leq  x\sum_{m=0}^{\lfloor n/3\rfloor} {n\choose m}
\leq  x\sum_{m=0}^{n} {n\choose m}
\leq  x\cdot 2^n.\]


The same calculation shows that $|Z_{n}(\beta)|$ and
$|Z_{n}(\overline{\beta})|$ are both upper-bounded by a sequence of
the form $c\cdot 2^n$, where $c$ is a real number independant from $n$.



Writing $S(\tau_{n+2})$ as
$\Sigma_{n}(\alpha)+\Sigma_{n}(\beta)+\Sigma_{n}(\overline{\beta})$,
we  get that $S(\tau_{n+2})=Z_{n}(\alpha)+c_{n}\cdot 2^n$, where
$c_{n}$ is uniformly bounded. Let us now study the sequence defined by 
$Z_{n}(\alpha)$. We have

\begin{eqnarray*}
\frac{Z_{n}(\alpha)}{\alpha^{n+2}}
&amp;=&amp;\sum_{m=0}^{\lfloor n/3\rfloor}{n\choose
m}(\alpha^{-3})^m-2\alpha^{-3}\sum_{m=0}^{\lfloor n/3\rfloor} {n\choose
m-1}(\alpha^{-3})^{m-1}\\
&amp;=&amp;{n\choose \lfloor n/3\rfloor}(\alpha^{-3})^{\lfloor n/3\rfloor}
+(1-2\alpha^{-3})
\sum_{m=0}^{\lfloor n/3\rfloor-1}{n\choose m}(\alpha^{-3})^m.
\end{eqnarray*}

Up to a multiplicative constant, 
the first term of the right side of the latter equality is, by
Stirling's formula, equivalent to
${\displaystyle\frac{1}{\sqrt{n}}\cdot\left(\frac{3}{2^{2/3}\alpha}
\right)^n}$, which tends to zero as $n$ goes to infinity. We can
therefore neglect this term, since the second one is lower-bounded by 
a positive constant.

Now, then, we focus our attention to this latter term, denoted by
${\tilde Z}_{n}$. Our aim is to
prove that it is exponentially increasing, with a growth rate equal to
$1+\alpha^{-3}$. Let assume first that $\lfloor(n+1)/3\rfloor=\lfloor
n/3\rfloor =k+1$. Then, we
have
\begin{eqnarray*}
\frac{{\tilde Z}_{n+1}}{{\tilde Z}_{n}} &amp;=&amp;
\frac{\sum_{m=0}^{k}{n+1\choose m}(\alpha^{-3})^m}{\sum_{m=0}^{k}
{n\choose m}(\alpha^{-3})^m}\\
&amp;=&amp;\frac{\sum_{m=0}^{k}({n\choose m}+{n\choose m-1})
(\alpha^{-3})^m}{\sum_{m=0}^{k}
{n\choose m}(\alpha^{-3})^m}\\
&amp;=&amp;1+\frac{\sum_{m=0}^{k}{n\choose m-1}(\alpha^{-3})^m}{\sum_{m=0}^{k}
{n\choose m}(\alpha^{-3})^m}\\
&amp;=&amp;1+\alpha^{-3}\frac{\sum_{m=0}^{k}{n\choose m-1}
(\alpha^{-3})^{m-1}}{\sum_{m=0}^{k}
{n\choose m}(\alpha^{-3})^m}\\
&amp;=&amp;1+\alpha^{-3}\frac{\sum_{m=0}^{k-1}{n\choose m}
(\alpha^{-3})^{m}}{\sum_{m=0}^{k}
{n\choose m}(\alpha^{-3})^m}\\
&amp;=&amp;1+\alpha^{-3}\left(1-\frac{{n\choose k}(\alpha^{-3})^k}{\sum_{m=0}^{k}
{n\choose m}(\alpha^{-3})^m}\right).
\end{eqnarray*}

In the last fraction, the numerator tends to zero (same proof as
before, with Stirling's formula) and the denominator is lower-bounded 
by $1$, so the fraction tends to zero as $n$ goes to infinity.

If $\lfloor (n+1)/3\rfloor =\lfloor n/3\rfloor +1=k+2$, then we 
simply have to add to the numerator 
of the first fraction the expression ${n+1\choose
k+1}(\alpha^{-3})^{k+1}$, which again tends to zero as $n$ goes to
infinity, and  can be neglected for that reason.

Thus, we  have proved that the sequence $(Z_{n})_{n}$ grows
exponentially to infinity with a growth rate equal to 
$\alpha(1+\alpha^{-3})$; so does the sequence $(S(\tau_{n}))_{n}$, since 
the term $c_{n}\cdot 2^n$ can be neglected. 
Using the relation $\alpha^3=2\alpha^2+1$,
we get that $\alpha(1+\alpha^{-3})=2(\alpha-1)$. It remains then to
divide this value by $2$, which gives $\alpha-1$, to obtain 
the growth rate of the average value of the $n$-th term of a
random Fibonacci sequence such that its first term is $1$ and
its second is $\varphi$ or $\varphi^{-1}$.

\subsection{Step 4: growth rate of $S(\tau_{n}^{(a,b)})$ for all pairs 
$(a,b)$}

For any pair $(a,b)$ such that $a\geq 0$, $b\geq 0$ and $ab\neq 0$, 
there exist two numbers $u$ and $v$ such that $uv\neq 0$ and such that
$(a,b)=u(1,\varphi)+v(1,\varphi^{-1})$. Thus, we have
\[S(\tau_{n}^{(a,b)})=uS(\tau_{n}^{(1,\varphi)})+
vS(\tau_{n}^{(1,\varphi^{-1})}).\]

Since  the sequences $(S(\tau_{n}^{(1,\varphi)}))_{n}$ and 
$(S(\tau_{n}^{(1,\varphi^{-1})}))_{n}$ both increase exponentially with
$2(\alpha-1)$ as growth rate, this is still the case for the sequence 
$(S(\tau_{n}^{(a,b)}))_{n}$. Dividing by $2$ the value $2(\alpha-1)$ to
get the average value of the $n$-th term, we obtain the result stated 
in Theorem \ref{Main1}.


\section{Interesting properties of ${\mathbf{R}}$ and related trees}

This section is devoted to some properties of ${\mathbf{R}}$ which seem of
interest to us. It  concerns the arithmetical properties of the nodes 
of the tree, some facts about continued fraction expansion, some
combinatorial properties, and also, for an important part, the link
between the tree and the sets $\SL(2,\N)$ and $\SL(2,\Z)$.

\subsection{Values in the $n$-th row of ${\mathbf{R}}$}

Lemma \ref{Uns} allows to know explicitly the numbers of $1$s in any 
row. Our aim is here to extend this result to the other numbers.

Let us recall that the {\em Euler
function} $\phi$ maps each positive integer $n$ to the number,
denoted by $\phi(n)$, 
of positive integers $k&lt;n$ such that $k$ and $n$ are relatively prime. 
(We fix the convention $\phi(1)=1$.)



\begin{Lemme}\label{MarchesEntiers}  Let $n\geq 1$ be an integer. The
nodes in ${\mathbf{R}}$ with value $n$ are included in a union of $2\phi(n)$ walks in
${\mathbf{R}}$.

\end{Lemme}

\begin{proof} The case $n=1$ is contained in Lemma \ref{Uns},
thus we assume $n\geq 2$. Let $k&lt;n$ be a positive integer prime with
$n$. By Proposition \ref{Containment}, the pairs $(n,k)$
and $(k,n)$ appear only once.

We start from the pair $(n,k)$. The walk
defined by the sequence of signs $+$ $-$ $+$ $+$ $-$ $+$ $+$ $-$ $+$ 
$+$ $-$ $+$ $+$\ldots shows successively the integers:
\[n+k\quad n\quad 2n+k\quad 3n+k\quad n\quad 4n+k\quad 5n+k\quad
n\quad 6n+k\quad 7n+k\quad n\ldots\]
\noindent so this walk shows all pairs of the form $(n,2mn+k)$ and
of the form $((2m+1)n+k,n)$, where $m$ is any integer, and shows no
other pair containing $n$.

In the same way, starting from $(k,n)$ and applying the sequence of
signs $-$ $+$ $-$ $+$ $+$ $-$ $+$ $+$ $-$ $+$ $+$ $-$ $+$\ldots (it is
allowed to start with a $-$ sign since, thanks to Lemma \ref{Ordre},
$n$ is necessarily a right child of $k$), we get the sequence of
integers:
\[n-k\quad 2n-k\quad n\quad 3n-k\quad 4n-k\quad n\quad 5n-k\quad
6n-k\quad n\ldots,\]
\noindent so this walk shows all pairs of the form $(n,2mn+(n-k))$
and of the form $((2m+1)n+(n-k),n)$, where $m$ is any integer, and
shows no other pair containing $n$.

The union of all these walks then show all appearing pairs in ${\mathbf{R}}$
containing $n$, and their cardinality is twice the number of integers 
$k&lt;n$ primes with $n$, so the lemma is proved.

\end{proof}

\begin{Lemme}\label{PositionsEntiers}  Let $n&gt;0$ be an integer. There
exists an integer $N(n)$ such that, for any $N\geq N(n)$, there are
exactly $2\phi(n)$ nodes equal to $n$ among the $N$-th, the $(N+1)$-th and the
$(N+2)$-th row of ${\mathbf{R}}$.


\end{Lemme}


\begin{Lemme}\label{Inclusion}  For any positive integer $N$, the
$N$-th row of ${\mathbf{R}}$ is included in the $(N+3)$-th one, that is if the
value $v$ appears $a$ times in the $N$-th row, then it appears at
least $a$ times in the $(N+3)$-th one.
\end{Lemme}

 Both of the two previous lemmas are immediate 
 consequences of the fact that each 
walk in Lemma \ref{MarchesEntiers} shows exactly two nodes between each value
$n$.





\begin{Prop}\label{SerieGen}  For all integers $k$ and $n$, let us
denote by $a_{k,n}$ the number of nodes of value $n$ in the $k$-th row
of ${\mathbf{R}}$. For all $k\geq 0$, 
we define the formal series $S_{k}(X)$ as 
$\sum_{n&gt;0}a_{k,n}X^n$. The sequence $(S_{k}(X)+S_{k+1}(X)+S_{k+2}(X))_{k}$ 
is increasing and admits as a limit the series
\[S(X):=2\sum_{n&gt;0}\phi(n)X^n.\]
\end{Prop}

\begin{proof} The fact that the formal series is increasing is a
consequence of Lemma \ref{Inclusion}. Lemma \ref{PositionsEntiers}
shows that, for any integer $n$, $a_{k,n}=2\phi(n)$ for all $k\geq
N(n)$, so the proposition is proved.
\end{proof}





Simple considerations of parity gives the following easy proposition, 
which allows to be a little more precise in the description of the
rows of ${\mathbf{R}}$:

\begin{Prop}\label{PairImpair}  The values of the nodes in the
$N$-th row of ${\mathbf{R}}$ are all even (resp. all odd) iff $N$ belongs (resp. 
does not belong) to $2+3\N$.
\end{Prop}

\begin{proof} The property is true for the first rows of ${\mathbf{R}}$. If 
the nodes of two consecutive rows are all odd, then, since the values 
of the nodes of the next row are all of the form $|a\pm b|$
where $a$ and $b$ are odd, all of theses values are even. In 
the same way, if all nodes of a row are even and all of the following 
(or previous) are odd, then the next row is made of odd values only,
and Proposition \ref{PairImpair} is proved.
\end{proof}


\subsection{Positions of $0$-nodes in ${\mathbf{T}}$}\label{Zeros}


By $0$-nodes of ${\mathbf{T}}$ we mean the nodes with value $0$. The aim of this
section is to determine their position in ${\mathbf{T}}$ in term of finite walks
$(w_{i})_{0\leq i\leq N}$.


\begin{Def}  A finite walk $(w_{i})_{0\leq i\leq N}$ 
such that the corresponding random Fibonacci sequence $(g_{i})_{0\leq 
i\leq N+2}$ 
verifies that $g_{i}= 0$ only for $i=N+2$ will be said 
a {\em single-$0$ walk}.
\end{Def}

By Proposition 
\ref{PairImpair}, if $(w_{i})_{0\leq i\leq N}$ is a
single-$0$ walk, then $N$ is of the form $3n$, where $n$ is an
integer.



\begin{Lemme}\label{TroisMoins} Let $(w_{i})_{0\leq i\leq N}$ be a
 single-$0$ walk such that $N&gt;0$. We have $w_{N}=w_{N-1}=w_{N-2}=-$.
\end{Lemme}

\begin{proof} By Proposition \ref{Containment}, $g_{N}=0$
implies $g_{N-1}=1$, and so $g_{N-2}=1$. Since
$g_{N-3}\neq 0$ by hypothesis, we have $g_{N-3}=2$. Finally, we get 
$w_{N}=w_{N-1}=w_{N-2}=-$.


\end{proof}

\begin{Prop}\label{Card}  A finite walk  $(w_{i})_{0\leq i\leq N}$ 
is a single-$0$  walk iff the inequality
\[\Card(\{0\leq j&lt;i\ :\ w_{j}=+\})\geq \frac{i}{3}\]

\noindent holds for all $i\leq N$ but not for $i=N+1$.

\end{Prop}


\begin{proof} The proposition is true for $N=0$. In the following, we
assume that the statement is true for finite walks of at most
$1+3(n-1)$ elements, where $n\geq 1$ is some integer.

Let us prove the implication. Consider a single-$0$ walk 
$(w_{i})_{0\leq i\leq N}$ where $N=3n$: since $N&gt;0$, we  have $w_{0}=+$. 
By Lemma \ref{TroisMoins}, the three last terms of the walk are minus 
signs, so there is at least one position in the walk 
where we find the succession  $+--$, which can be removed thanks to
the considerations made in section \ref{TR}. We then get a single-$0$ 
walk $({\tilde w}_{i})_{0\leq i\leq N-3}$ which, by induction 
hypothesis, verifies the cardinality property stated 
in the proposition. The re-introduction of the sequence $+--$ does not
modify the validity of this cardinality property, so the walk 
$(w_{i})_{0\leq i\leq N}$ verifies this cardinality property.

Conversely, let assume that a walk $(w_{i})_{0\leq i\leq N}$ (with
$N=3n$) verifies the cardinality property. We thus have $w_{N}=-$, and
there must be exactly $n$ plus signs and $2n$ minus signs among the
$w_{i}$s for $i\in [0,3n-1]$. Consequently, the sequence $+--$ must
appear somewhere. Suppress it: the cardinality property remains true
for the new sequence, which is therefore a single-$0$ walk by the
induction hypothesis.
Re-introducing the $+--$ does not introduce one more $0$ in the random
Fibonacci sequence, so the full 
sequence $(w_{i})_{0\leq i\leq N}$ is also a single-$0$ walk, and the 
proposition is proved.
\end{proof}

\begin{Cor}\label{FormeZero}  A single-$0$ walk $(w_{i})_{0\leq
i\leq 3n}$  contains $n$ plus signs and $2n+1$ minus signs.

\end{Cor}




The  property mentioned in the previous proposition has for
consequence the following (see the sequence \seqnum{A001764} in 
 \cite{EIT} for details and references):

\begin{Prop}\label{NbMarchesZero}  Let us denote by $\omega_{n}$ the 
number of single-$0$ walks $(w_{i})_{0\leq
i\leq 3n}$. We have

\[\omega_{n}=\frac{1}{2n+1}{3n \choose n}.\]



\end{Prop}


We can deduce from what precedes the following description of walks
$(w_{i})_{0\leq i\leq N}$ such that $w_{N}=0$ (without necessarily
$w_{i}\neq 0$ for $i&lt;N$). Let us give it briefly: we 
denote by $z_{1}$, $z_{2}$, $z_{3}$\ldots the
increasing values between $0$ and $N$ such that $g_{z_{1}+2}=
g_{z_{2}+2}=g_{z_{3}+2}=\cdots=0$. Then, the walks defined by $(w_{i})_{0\leq
i\leq z_{1}}$, $(w_{i})_{z_{1}+3\leq i\leq z_{2}}$,
$(w_{i})_{z_{2}+3\leq i\leq z_{3}}$,
\ldots are
single-$0$ walks (and, thus can be described 
 with the use of Proposition \ref{Card}), and the
elements $w_{z_{1}+1}$, $w_{z_{1}+2}$, $w_{z_{2}+1}$, $w_{z_{2}+2}$, 
$w_{z_{3}+1}$, $w_{z_{3}+2}$\ldots
are allowed to be plus or minus signs without condition.





\subsection{The matrix point of view}\label{Matrices}


Let us keep the nodes and edges of ${\mathbf{R}}$ and the rules for the values at 
each node, but let us replace the first appearing pair $(1,1)$ by
formal expressions $a$ and $b$, to get the following tree:

\begin{figure}[H]
{\hskip 0.9in}
\begin{graph}(19,10)(2.5,1)
\newcommand{\node}[4]{%
\textnode #1(#2,#3){#4}[\graphlinecolour{1}]}

\node{Racine}{6.61875}{10}{$a$}

\node{Fils}{6.61875}{9}{$b$}

\node{L1n1}{6.61875}{8}{$a+b$}

\node{L2n1}{2.455}{7}{$a$}
\node{L2n2}{10.7825}{7}{$a+2b$}

\node{L3n1}{2.455}{6}{$2a+b$}
\node{L3n2}{8.24}{6}{$b$}
\node{L3n3}{13.325}{6}{$2a+3b$}

\node{L4n1}{0.86}{5}{$a+b$}
\node{L4n2}{4.05}{5}{$3a+b$}
\node{L4n3}{8.24}{5}{$a+3b$}
\node{L4n4}{11.74}{5}{$a+b$}
\node{L4n5}{14.91}{5}{$3a+5b$}


\node{L5n1}{0.86}{4}{$3a+2b$}
\node{L5n2}{3.08}{4}{$a$}
\node{L5n3}{5.02}{4}{$5a+2b$}
\node{L5n4}{7.24}{4}{$a+2b$}
\node{L5n5}{9.18}{4}{$a+4b$}
\node{L5n6}{11.74}{4}{$3a+4b$}
\node{L5n7}{13.92}{4}{$a+2b$}
\node{L5n8}{15.9}{4}{$5a+8b$}



\node{L6n1}{0.24}{3}{\footnotesize $2a+b$}
\node{L6n2}{1.48}{3}{\footnotesize $4a+3b$}
\node{L6n3}{3.08}{3}{\footnotesize $4a+b$}
\node{L6n4}{4.4}{3}{\footnotesize $2a+b$}
\node{L6n5}{5.64}{3}{\footnotesize $8a+3b$}
\node{L6n6}{7.24}{3}{\footnotesize $2a+5b$}
\node{L6n7}{8.56}{3}{\footnotesize $b$}
\node{L6n8}{9.8}{3}{\footnotesize $2a+7b$}
\node{L6n9}{11.12}{3}{\footnotesize $2a+3b$}
\node{L6n10}{12.36}{3}{\footnotesize $4a+5b$}
\node{L6n11}{13.92}{3}{\footnotesize $4a+7b$}
\node{L6n12}{15.28}{3}{\footnotesize $2a+3b$}
\node{L6n13}{16.52}{3}{\footnotesize $8a+13b$}




\edge{Racine}{Fils}

\edge{Fils}{L1n1}

\edge{L1n1}{L2n1}
\edge{L1n1}{L2n2}

\edge{L2n1}{L3n1}
\edge{L2n2}{L3n2}
\edge{L2n2}{L3n3}

\edge{L3n1}{L4n1}
\edge{L3n1}{L4n2}
\edge{L3n2}{L4n3}
\edge{L3n3}{L4n4}
\edge{L3n3}{L4n5}

\edge{L4n1}{L5n1}
\edge{L4n2}{L5n2}
\edge{L4n2}{L5n3}
\edge{L4n3}{L5n4}
\edge{L4n3}{L5n5}
\edge{L4n4}{L5n6}
\edge{L4n5}{L5n7}
\edge{L4n5}{L5n8}


\edge{L5n1}{L6n1}
\edge{L5n1}{L6n2}
\edge{L5n2}{L6n3}
\edge{L5n3}{L6n4}
\edge{L5n3}{L6n5}
\edge{L5n4}{L6n6}
\edge{L5n5}{L6n7}
\edge{L5n5}{L6n8}
\edge{L5n6}{L6n9}
\edge{L5n6}{L6n10}
\edge{L5n7}{L6n11}
\edge{L5n8}{L6n12}
\edge{L5n8}{L6n13}



\end{graph}



\caption{The general restricted tree ${\mathbf{R}}_{(a,b)}$}

\end{figure}



It is easily seen that, for any nonegative $a$ and $b$, 
all the recurrence relations given previously concerning sum of rows remain 
true, up to a change in initial values of those sequences.



Lemma \ref{StructAsc} leaves to the following
interpretation of this tree in terms of elements of $\SL(2,\N)$: the 
nodes of the general restricted tree are all of the form $ma+nb$. 
We deduce from this tree another tree 
in which the edge joining the nodes $ma+nb$ and
$m'a+n'b$ is labelled by the matrix
$\left(\begin{array}{cc}m&amp;n\\m'&amp;n'\end{array}\right)$, which belongs to
$\SL(2,\Z)$ by Lemma \ref{StructAsc}.


\begin{figure}[H]
{\vskip 0.5in}
{\hskip 0.9in}
\begin{graph}(19,10)(2.5,-2)
\newcommand{\node}[4]{%
\roundnode #1(#2,#3)[\graphlinecolour{1}]}

\node{Racine}{6.61875}{10}

\node{Fils}{6.61875}{8}

\node{L1n1}{6.61875}{6}

\node{L2n1}{2.455}{4}{}
\node{L2n2}{10.7825}{4}{}

\node{L3n1}{2.455}{2}{}
\node{L3n2}{8.24}{2}{}
\node{L3n3}{13.325}{2}{}

\node{L4n1}{0.66}{0}{}
\node{L4n2}{4.05}{0}{}
\node{L4n3}{8.24}{0}{}
\node{L4n4}{11.52}{0}{}
\node{L4n5}{14.91}{0}{}


\node{L5n1}{0.66}{-2}{}
\node{L5n2}{2.7}{-2}{}
\node{L5n3}{5.4}{-2}{}
\node{L5n4}{6.86}{-2}{}
\node{L5n5}{9.56}{-2}{}
\node{L5n6}{11.52}{-2}{}
\node{L5n7}{13.54}{-2}{}
\node{L5n8}{16.28}{-2}{}



\edge{Racine}{Fils}
\edgetext{Racine}{Fils}{$\left(\begin{array}{cc}1&amp;0\\
0&amp;1\end{array}\right)$}

\edge{Fils}{L1n1}
\edgetext{Fils}{L1n1}{$\left(\begin{array}{cc}0&amp;1\\
1&amp;1\end{array}\right)$}

\edge{L1n1}{L2n1}
\edge{L1n1}{L2n2}
\edgetext{L1n1}{L2n1}{$\left(\begin{array}{cc}1&amp;1\\
1&amp;0\end{array}\right)$}
\edgetext{L1n1}{L2n2}{$\left(\begin{array}{cc}1&amp;1\\
1&amp;2\end{array}\right)$}

\edge{L2n1}{L3n1}
\edge{L2n2}{L3n2}
\edge{L2n2}{L3n3}
\edgetext{L2n1}{L3n1}{$\left(\begin{array}{cc}1&amp;0\\
2&amp;1\end{array}\right)$}
\edgetext{L2n2}{L3n2}{$\left(\begin{array}{cc}1&amp;2\\
0&amp;1\end{array}\right)$}
\edgetext{L2n2}{L3n3}{$\left(\begin{array}{cc}1&amp;2\\
2&amp;3\end{array}\right)$}

\edge{L3n1}{L4n1}
\edge{L3n1}{L4n2}
\edge{L3n2}{L4n3}
\edge{L3n3}{L4n4}
\edge{L3n3}{L4n5}
\edgetext{L3n1}{L4n1}{$\left(\begin{array}{cc}2&amp;1\\
1&amp;1\end{array}\right)$}
\edgetext{L3n1}{L4n2}{$\left(\begin{array}{cc}2&amp;1\\
3&amp;1\end{array}\right)$}
\edgetext{L3n2}{L4n3}{$\left(\begin{array}{cc}0&amp;1\\
1&amp;3\end{array}\right)$}
\edgetext{L3n3}{L4n4}{$\left(\begin{array}{cc}2&amp;3\\
1&amp;1\end{array}\right)$}
\edgetext{L3n3}{L4n5}{$\left(\begin{array}{cc}2&amp;3\\
3&amp;5\end{array}\right)$}

\edge{L4n1}{L5n1}
\edge{L4n2}{L5n2}
\edge{L4n2}{L5n3}
\edge{L4n3}{L5n4}
\edge{L4n3}{L5n5}
\edge{L4n4}{L5n6}
\edge{L4n5}{L5n7}
\edge{L4n5}{L5n8}
\edgetext{L4n1}{L5n1}{\tiny $\left(\begin{array}{cc}1&amp;1\\
3&amp;2\end{array}\right)$}
\edgetext{L4n2}{L5n2}{\tiny $\left(\begin{array}{cc}3&amp;1\\
1&amp;0\end{array}\right)$}
\edgetext{L4n2}{L5n3}{\tiny $\left(\begin{array}{cc}3&amp;1\\
5&amp;2\end{array}\right)$}
\edgetext{L4n3}{L5n4}{\tiny $\left(\begin{array}{cc}1&amp;3\\
1&amp;2\end{array}\right)$}
\edgetext{L4n3}{L5n5}{\tiny $\left(\begin{array}{cc}1&amp;3\\
1&amp;4\end{array}\right)$}
\edgetext{L4n4}{L5n6}{\tiny $\left(\begin{array}{cc}1&amp;1\\
3&amp;4\end{array}\right)$}
\edgetext{L4n5}{L5n7}{\tiny $\left(\begin{array}{cc}3&amp;5\\
1&amp;2\end{array}\right)$}
\edgetext{L4n5}{L5n8}{\tiny $\left(\begin{array}{cc}3&amp;5\\
5&amp;8\end{array}\right)$}


\end{graph}

\caption{The $\SL(2,\N)$ tree}
\end{figure}


\begin{Prop}\label{SL2}  The latter tree is composed of all elements of
$\SL(2,\N)$, each appearing exactly once.
\end{Prop}

\begin{proof} The fact that the coefficients of all the matrices 
are nonnegative is a consequence of Lemma \ref{StructAsc}. The fact
that each matrice cannot appear twice is a consequence of the
non-redundance property of ${\mathbf{R}}$. Finally, if
$\left(\begin{array}{cc}m&amp;n\\m'&amp;n'\end{array}\right)\in\SL(2,\N)$,
then the characterization of walks in ${\mathbf{R}}$ (Corollary
\ref{PropFond}) suggests to consider the matrix 
$\left(\begin{array}{cc}|m-m'|&amp;|n-n'|\\m&amp;n\end{array}\right)$ as its 
parent. Pursuing in the same way, by 
induction we construct an effective walk in the tree which leads to 
the desired matrix, and the proposition is proved.
\end{proof}


\begin{Prop}\label{Trans}  If $M\in\SL(2,\N)$ is attained by the
walk $(w_{i})_{0\leq i\leq n}$ in the tree, then
$M^T$ is attained by the walk $(w_{n-i})_{0\leq i\leq n}$.
(In particular, $M$ and $M^T$ appears at the same row in the
$\SL(2,\N)$ tree).

\end{Prop}

\begin{proof} Let us denote by $M:=\left(\begin{array}{cc} m&amp;n \\ m'&amp;
n'\end{array}\right)$ the label of an edge. 
The right child of $M$ is the matrix
$DM$, where $D=\left(\begin{array}{cc} 0&amp;1 \\ 1&amp;
1\end{array}\right)$. 

By Lemma \ref{StructAsc}, 
if $m&gt;m'$ then $n\geq n'$ and if $n&gt;n'$ then $m\geq m'$. In
particular, if $m&gt;m'$ then $m+n&gt;m'+n'$ and $M$ has no left child (take
$a=b=1$ and use Lemma \ref{Ordre}). For the same reason, if $n&gt;n'$
then $M$ has no left child. So if $M$ has a left child, then
$m\leq m'$ and $n\leq n'$ and, since we cannot have $m=m'$ and $n=n'$ 
(because of the relation $mn'-m'n=\pm 1$), Lemma \ref{Ordre} shows
that this is a sufficient condition. A 
simple calculation shows that, in this case, the 
left child of $M$ is given by $GM$, where $G=
\left(\begin{array}{cc} 0&amp;1 \\ -1&amp;
1\end{array}\right)$.

Any matrix $M$ of the $\SL(2,\N)$ tree can
therefore be written as a product of the form $G^{\gamma_{0}}D^{\delta_{0}}
GD^{\delta_{1}}\cdots GD^{\delta_{k-1}}GD^{\delta_{k}}\cdot 
\left(\begin{array}{cc} 0&amp;1 \\ 1&amp;
1\end{array}\right)$, where $\gamma_{0}=0$ or $1$, $\delta_{i}&gt;0$
for all $i$ between $0$ and $k-1$ and $\delta_{k}\geq 0$. The matrix 
$\left(\begin{array}{cc} 0&amp;1 \\ 1&amp;
1\end{array}\right)$ corresponds to the child of the identity matrix 
in the $\SL(2,\N)$ tree and is simply equal to $D$. 

We remark that $D^T=D$ and that, as a simple computation shows,
$G^T=D^{-1}GD$, so we get 
\begin{eqnarray*}
M^T&amp;=&amp;(G^{\gamma_{0}}D^{\delta_{0}}
GD^{\delta_{1}}\cdots GD^{\delta_{k-1}}GD^{\delta_{k}}\cdot
D)^T\\
&amp;=&amp;D\cdot D^{\delta_{k}}{}^tGD^{\delta_{k-1}}{}^tG\cdots
D^{\delta_{1}}{}^tGD^{\delta_{0}}{}^tG^{\gamma_{0}}\\
&amp;=&amp;D^{\delta_{k}+1}(D^{-1}GD)D^{\delta_{k-1}}(D^{-1}GD)\cdots
D^{\delta_{1}}(D^{-1}GD)D^{\delta_{0}}(D^{-1}GD)^{\gamma_{0}}\\
&amp;=&amp;D^{\delta_{k}}GD^{\delta_{k-1}}G\cdots
D^{\delta_{1}}GD^{1+\delta_{0}-\gamma_{0}}G^{\gamma_{0}}D^{\gamma_{0}}.
\end{eqnarray*}

It is then routinely verified that, in the case $\gamma_{0}=0$ as
well as in the case $\gamma_{0}=1$, this latter expression is equal to 
$D^{\delta_{k}}GD^{\delta_{k-1}}G\cdots
D^{\delta_{1}}GD^{\delta_{0}}G^{\gamma_{0}}\cdot D$, and the proposition is 
proved.
\end{proof}

The following tree is deduced from the previous one, each matrix
being replaced by the sign of its determinant.

\begin{figure}[H]
{\vskip .3in}{\hskip 0.9in}
\begin{graph}(19,10)(2.5,0)
\newcommand{\node}[3]{%
\roundnode #1(#2,#3)[\graphlinecolour{1}]}

\node{Racine}{6.61875}{10}

\node{Fils}{6.61875}{9}

\node{L1n1}{6.61875}{8}

\node{L2n1}{2.455}{7}
\node{L2n2}{10.7825}{7}

\node{L3n1}{2.455}{6}
\node{L3n2}{8.24}{6}
\node{L3n3}{13.325}{6}

\node{L4n1}{0.86}{5}
\node{L4n2}{4.05}{5}
\node{L4n3}{8.24}{5}
\node{L4n4}{11.74}{5}
\node{L4n5}{14.91}{5}


\node{L5n1}{0.86}{4}
\node{L5n2}{3.08}{4}
\node{L5n3}{5.02}{4}
\node{L5n4}{7.24}{4}
\node{L5n5}{9.18}{4}
\node{L5n6}{11.74}{4}
\node{L5n7}{13.92}{4}
\node{L5n8}{15.9}{4}



\node{L6n1}{0.24}{3}
\node{L6n2}{1.48}{3}
\node{L6n3}{3.08}{3}
\node{L6n4}{4.4}{3}
\node{L6n5}{5.64}{3}
\node{L6n6}{7.24}{3}
\node{L6n7}{8.56}{3}
\node{L6n8}{9.8}{3}
\node{L6n9}{11.12}{3}
\node{L6n10}{12.36}{3}
\node{L6n11}{13.92}{3}
\node{L6n12}{15.28}{3}
\node{L6n13}{16.52}{3}





\node{L7n1}{0.24}{2}
\node{L7n2}{1.12}{2}
\node{L7n3}{1.84}{2}
\node{L7n4}{2.72}{2}
\node{L7n5}{3.44}{2}
\node{L7n6}{4.4}{2}
\node{L7n7}{5.28}{2}
\node{L7n8}{6}{2}
\node{L7n9}{6.88}{2}
\node{L7n10}{7.6}{2}
\node{L7n11}{8.56}{2}
\node{L7n12}{9.44}{2}
\node{L7n13}{10.16}{2}
\node{L7n14}{11.12}{2}
\node{L7n15}{12}{2}
\node{L7n16}{12.72}{2}
\node{L7n17}{13.6}{2}
\node{L7n18}{14.32}{2}
\node{L7n19}{15.28}{2}
\node{L7n20}{16.16}{2}
\node{L7n21}{16.88}{2}



\edge{Racine}{Fils}
\edgetext{Racine}{Fils}{+}


\edge{Fils}{L1n1}
\edgetext{Fils}{L1n1}{-}

\edge{L1n1}{L2n1}
\edge{L1n1}{L2n2}
\edgetext{L1n1}{L2n1}{-}
\edgetext{L1n1}{L2n2}{+}

\edge{L2n1}{L3n1}
\edge{L2n2}{L3n2}
\edge{L2n2}{L3n3}
\edgetext{L2n1}{L3n1}{+}
\edgetext{L2n2}{L3n2}{+}
\edgetext{L2n2}{L3n3}{-}

\edge{L3n1}{L4n1}
\edge{L3n1}{L4n2}
\edge{L3n2}{L4n3}
\edge{L3n3}{L4n4}
\edge{L3n3}{L4n5}
\edgetext{L3n1}{L4n1}{+}
\edgetext{L3n1}{L4n2}{-}
\edgetext{L3n2}{L4n3}{-}
\edgetext{L3n3}{L4n4}{-}
\edgetext{L3n3}{L4n5}{+}

\edge{L4n1}{L5n1}
\edge{L4n2}{L5n2}
\edge{L4n2}{L5n3}
\edge{L4n3}{L5n4}
\edge{L4n3}{L5n5}
\edge{L4n4}{L5n6}
\edge{L4n5}{L5n7}
\edge{L4n5}{L5n8}
\edgetext{L4n1}{L5n1}{-}
\edgetext{L4n2}{L5n2}{-}
\edgetext{L4n2}{L5n3}{+}
\edgetext{L4n3}{L5n4}{-}
\edgetext{L4n3}{L5n5}{+}
\edgetext{L4n4}{L5n6}{+}
\edgetext{L4n5}{L5n7}{+}
\edgetext{L4n5}{L5n8}{-}


\edge{L5n1}{L6n1}
\edge{L5n1}{L6n2}
\edge{L5n2}{L6n3}
\edge{L5n3}{L6n4}
\edge{L5n3}{L6n5}
\edge{L5n4}{L6n6}
\edge{L5n5}{L6n7}
\edge{L5n5}{L6n8}
\edge{L5n6}{L6n9}
\edge{L5n6}{L6n10}
\edge{L5n7}{L6n11}
\edge{L5n8}{L6n12}
\edge{L5n8}{L6n13}
\edgetext{L5n1}{L6n1}{-}
\edgetext{L5n1}{L6n2}{+}
\edgetext{L5n2}{L6n3}{+}
\edgetext{L5n3}{L6n4}{+}
\edgetext{L5n3}{L6n5}{-}
\edgetext{L5n4}{L6n6}{+}
\edgetext{L5n5}{L6n7}{+}
\edgetext{L5n5}{L6n8}{-}
\edgetext{L5n6}{L6n9}{+}
\edgetext{L5n6}{L6n10}{-}
\edgetext{L5n7}{L6n11}{-}
\edgetext{L5n8}{L6n12}{-}
\edgetext{L5n8}{L6n13}{+}


\edge{L6n1}{L7n1}
\edge{L6n2}{L7n2}
\edge{L6n2}{L7n3}
\edge{L6n3}{L7n4}
\edge{L6n3}{L7n5}
\edge{L6n4}{L7n6}
\edge{L6n5}{L7n7}
\edge{L6n5}{L7n8}
\edge{L6n6}{L7n9}
\edge{L6n6}{L7n10}
\edge{L6n7}{L7n11}
\edge{L6n8}{L7n12}
\edge{L6n8}{L7n13}
\edge{L6n9}{L7n14}
\edge{L6n10}{L7n15}
\edge{L6n10}{L7n16}
\edge{L6n11}{L7n17}
\edge{L6n11}{L7n18}
\edge{L6n12}{L7n19}
\edge{L6n13}{L7n20}
\edge{L6n13}{L7n21}
\edgetext{L6n1}{L7n1}{+}
\edgetext{L6n2}{L7n2}{+}
\edgetext{L6n2}{L7n3}{-}
\edgetext{L6n3}{L7n4}{+}
\edgetext{L6n3}{L7n5}{-}
\edgetext{L6n4}{L7n6}{-}
\edgetext{L6n5}{L7n7}{-}
\edgetext{L6n5}{L7n8}{+}
\edgetext{L6n6}{L7n9}{+}
\edgetext{L6n6}{L7n10}{-}
\edgetext{L6n7}{L7n11}{-}
\edgetext{L6n8}{L7n12}{-}
\edgetext{L6n8}{L7n13}{+}
\edgetext{L6n9}{L7n14}{-}
\edgetext{L6n10}{L7n15}{-}
\edgetext{L6n10}{L7n16}{+}
\edgetext{L6n11}{L7n17}{-}
\edgetext{L6n11}{L7n18}{+}
\edgetext{L6n12}{L7n19}{+}
\edgetext{L6n13}{L7n20}{+}
\edgetext{L6n13}{L7n21}{-}

\end{graph}

\caption{The determinants tree}
\end{figure}


The structure of the plus and minus signs is given by the following
rules, routinely proved:


\begin{Prop}\label{ReglePlusOuMoins}  Let $\varepsilon\in\{-,+\}$ 
be the label of
an edge. The right edge following it is labelled $-\varepsilon$ and
the left one (if it exists) by $\varepsilon$.
\end{Prop}

As a corollary, we  get the number of $+$ and $-$ in each row of
the tree:

\begin{Cor}\label{NbPlusOuMoins} The number of plus signs at the
$n$-th row is $F_{n}/2$ if $n$ is of the form $3k$, $\lfloor
F_{n}/2\rfloor +1$ if
$n$ is of the form $3k+1$, and $\lfloor F_{n}/2\rfloor$ if $n$ is of the form
$3k+2$.

\end{Cor}

\begin{proof} Let us consider the $n$-th row of the tree; we 
denote by $d_{n}^+$ (resp. $d_{n}^-$) 
its number of right edges labelled $+$ (resp. $-$) and by $g_{n}^+$
(resp. $g_{n}^-$) the number of left edges labelled $+$ (resp. $-$).
Proposition \ref{Fib} easily gives the following relations for all
$n$:
\[d_{n}^++d_{n}^-=F_{n-1}\quad\mbox{and}\quad g_{n}^++g_{n}^-=F_{n-2}.\]

The structure of the tree, together with Proposition
\ref{ReglePlusOuMoins}, also give the following:
\[d_{n+1}^+=g_{n}^-+d_{n}^-\quad d_{n+1}^-=g_{n}^++d_{n}^+,\]
\[g_{n+1}^+=d_{n}^+\quad g_{n+1}^-=d_{n}^-.\]

We deduce from those relations that
$d_{n+1}^++g_{n+1}^+=F_{n-1}+g_{n}^-$ and that 
$d_{n+1}^-+g_{n+1}^-=F_{n-1}+g_{n}^+$. If we denote by $e_{n}$ the
difference $g_{n}^+-g_{n}^-$, then we get
\begin{eqnarray*}
e_{n}=g_{n}^+-g_{n}^-&amp;=&amp;d_{n-1}^+-d_{n-1}^-\\
&amp;=&amp;(g_{n-2}^-+d_{n-2}^-)-(g_{n-2}^++d_{n-2}^+)\\
&amp;=&amp;-e_{n-2}-(d_{n-2}^+-d_{n-2}^-)\\
&amp;=&amp;-e_{n-2}-(g_{n-1}^+-g_{n-1}^-)\\
&amp;=&amp;-(e_{n-2}+e_{n-1}).
\end{eqnarray*}

Since an immediate computation shows that $e_{3}=-1$ and $e_{4}=0$, we
easily get that the sequence $(e_{n})_{n\geq 3}$ is simply the sequence
$-1$, $0$, $1$, $-1$, $0$, $1$, etc., and the conclusion follows.
\end{proof}








An immediate consequence of the  rules given in Proposition
\ref{ReglePlusOuMoins} is that the infinite
words in $\{-,+\}$ given by walks in the determinant 
tree are exactly those which 
never show the sequence $- - -$ neither $+++$. In particular:

\begin{Prop}\label{BijMots}  In $\{-,+\}^{\N}$ equipped with the
cylinder topology, let us denote by ${\cal D}$ the subset of words who
does not show anywhere the succession $- - -$ or $+++$, and by ${\cal 
W}$
the subset of all words which never show the succession $- -$. To any 
$w\in {\cal W}$ we associate its corresponding walk in ${\mathbf{R}}$, then make 
the codage $d\in {\cal D}$ corresponding to the determinants of the
edges of ${\mathbf{R}}$. Thus, the defined function  $\phi$\ :\ 
${\cal W}\longrightarrow {\cal D}$ is bijective. Moreover, the $n$
first letters of $\phi(w)$ depends only on the $n$ first letters of
$w$, and conversely the $n$ first letters of $d$ depends only on
those of $\phi^{-1}(d)$. In particular, $\phi$
is bicontinuous.

\end{Prop}

Finally, the next tree is obtained by replacing each matrix by its
trace.

\begin{figure}[H]
{\hskip 0.7in}
\begin{graph}(19,10)(2.5,1)
\newcommand{\node}[3]{%
\roundnode #1(#2,#3)[\graphlinecolour{1}]}

\node{Racine}{6.61875}{10}

\node{Fils}{6.61875}{9}

\node{L1n1}{6.61875}{8}

\node{L2n1}{2.455}{7}
\node{L2n2}{10.7825}{7}

\node{L3n1}{2.455}{6}
\node{L3n2}{8.24}{6}
\node{L3n3}{13.325}{6}

\node{L4n1}{0.86}{5}
\node{L4n2}{4.05}{5}
\node{L4n3}{8.24}{5}
\node{L4n4}{11.74}{5}
\node{L4n5}{14.91}{5}


\node{L5n1}{0.86}{4}
\node{L5n2}{3.08}{4}
\node{L5n3}{5.02}{4}
\node{L5n4}{7.24}{4}
\node{L5n5}{9.18}{4}
\node{L5n6}{11.74}{4}
\node{L5n7}{13.92}{4}
\node{L5n8}{15.9}{4}



\node{L6n1}{0.24}{3}
\node{L6n2}{1.48}{3}
\node{L6n3}{3.08}{3}
\node{L6n4}{4.4}{3}
\node{L6n5}{5.64}{3}
\node{L6n6}{7.24}{3}
\node{L6n7}{8.56}{3}
\node{L6n8}{9.8}{3}
\node{L6n9}{11.12}{3}
\node{L6n10}{12.36}{3}
\node{L6n11}{13.92}{3}
\node{L6n12}{15.28}{3}
\node{L6n13}{16.52}{3}





\node{L7n1}{0.24}{2}
\node{L7n2}{1.12}{2}
\node{L7n3}{1.84}{2}
\node{L7n4}{2.72}{2}
\node{L7n5}{3.44}{2}
\node{L7n6}{4.4}{2}
\node{L7n7}{5.28}{2}
\node{L7n8}{6}{2}
\node{L7n9}{6.88}{2}
\node{L7n10}{7.6}{2}
\node{L7n11}{8.56}{2}
\node{L7n12}{9.44}{2}
\node{L7n13}{10.16}{2}
\node{L7n14}{11.12}{2}
\node{L7n15}{12}{2}
\node{L7n16}{12.72}{2}
\node{L7n17}{13.6}{2}
\node{L7n18}{14.32}{2}
\node{L7n19}{15.28}{2}
\node{L7n20}{16.04}{2}
\node{L7n21}{17.00}{2}



\edge{Racine}{Fils}
\edgetext{Racine}{Fils}{2}


\edge{Fils}{L1n1}
\edgetext{Fils}{L1n1}{1}

\edge{L1n1}{L2n1}
\edge{L1n1}{L2n2}
\edgetext{L1n1}{L2n1}{1}
\edgetext{L1n1}{L2n2}{3}

\edge{L2n1}{L3n1}
\edge{L2n2}{L3n2}
\edge{L2n2}{L3n3}
\edgetext{L2n1}{L3n1}{2}
\edgetext{L2n2}{L3n2}{2}
\edgetext{L2n2}{L3n3}{4}

\edge{L3n1}{L4n1}
\edge{L3n1}{L4n2}
\edge{L3n2}{L4n3}
\edge{L3n3}{L4n4}
\edge{L3n3}{L4n5}
\edgetext{L3n1}{L4n1}{3}
\edgetext{L3n1}{L4n2}{3}
\edgetext{L3n2}{L4n3}{3}
\edgetext{L3n3}{L4n4}{3}
\edgetext{L3n3}{L4n5}{7}

\edge{L4n1}{L5n1}
\edge{L4n2}{L5n2}
\edge{L4n2}{L5n3}
\edge{L4n3}{L5n4}
\edge{L4n3}{L5n5}
\edge{L4n4}{L5n6}
\edge{L4n5}{L5n7}
\edge{L4n5}{L5n8}
\edgetext{L4n1}{L5n1}{3}
\edgetext{L4n2}{L5n2}{3}
\edgetext{L4n2}{L5n3}{5}
\edgetext{L4n3}{L5n4}{3}
\edgetext{L4n3}{L5n5}{5}
\edgetext{L4n4}{L5n6}{5}
\edgetext{L4n5}{L5n7}{5}
\edgetext{L4n5}{L5n8}{11}


\edge{L5n1}{L6n1}
\edge{L5n1}{L6n2}
\edge{L5n2}{L6n3}
\edge{L5n3}{L6n4}
\edge{L5n3}{L6n5}
\edge{L5n4}{L6n6}
\edge{L5n5}{L6n7}
\edge{L5n5}{L6n8}
\edge{L5n6}{L6n9}
\edge{L5n6}{L6n10}
\edge{L5n7}{L6n11}
\edge{L5n8}{L6n12}
\edge{L5n8}{L6n13}
\edgetext{L5n1}{L6n1}{4}
\edgetext{L5n1}{L6n2}{6}
\edgetext{L5n2}{L6n3}{2}
\edgetext{L5n3}{L6n4}{6}
\edgetext{L5n3}{L6n5}{8}
\edgetext{L5n4}{L6n6}{6}
\edgetext{L5n5}{L6n7}{2}
\edgetext{L5n5}{L6n8}{8}
\edgetext{L5n6}{L6n9}{6}
\edgetext{L5n6}{L6n10}{8}
\edgetext{L5n7}{L6n11}{8}
\edgetext{L5n8}{L6n12}{8}
\edgetext{L5n8}{L6n13}{18}


\edge{L6n1}{L7n1}
\edge{L6n2}{L7n2}
\edge{L6n2}{L7n3}
\edge{L6n3}{L7n4}
\edge{L6n3}{L7n5}
\edge{L6n4}{L7n6}
\edge{L6n5}{L7n7}
\edge{L6n5}{L7n8}
\edge{L6n6}{L7n9}
\edge{L6n6}{L7n10}
\edge{L6n7}{L7n11}
\edge{L6n8}{L7n12}
\edge{L6n8}{L7n13}
\edge{L6n9}{L7n14}
\edge{L6n10}{L7n15}
\edge{L6n10}{L7n16}
\edge{L6n11}{L7n17}
\edge{L6n11}{L7n18}
\edge{L6n12}{L7n19}
\edge{L6n13}{L7n20}
\edge{L6n13}{L7n21}
\edgetext{L6n1}{L7n1}{\footnotesize 5}
\edgetext{L6n2}{L7n2}{\footnotesize 5}
\edgetext{L6n2}{L7n3}{\footnotesize 9}
\edgetext{L6n3}{L7n4}{\footnotesize 5}
\edgetext{L6n3}{L7n5}{\footnotesize 5}
\edgetext{L6n4}{L7n6}{\footnotesize 5}
\edgetext{L6n5}{L7n7}{\footnotesize 9}
\edgetext{L6n5}{L7n8}{\footnotesize 13}
\edgetext{L6n6}{L7n9}{\footnotesize 5}
\edgetext{L6n6}{L7n10}{\footnotesize 9}
\edgetext{L6n7}{L7n11}{\footnotesize 5}
\edgetext{L6n8}{L7n12}{\footnotesize 5}
\edgetext{L6n8}{L7n13}{\footnotesize 13}
\edgetext{L6n9}{L7n14}{\footnotesize 9}
\edgetext{L6n10}{L7n15}{\footnotesize 5}
\edgetext{L6n10}{L7n16}{\footnotesize 13}
\edgetext{L6n11}{L7n17}{\footnotesize 9}
\edgetext{L6n11}{L7n18}{\footnotesize 13}
\edgetext{L6n12}{L7n19}{\footnotesize 13}
\edgetext{L6n13}{L7n20}{\footnotesize 13}
\edgetext{L6n13}{L7n21}{\footnotesize 29}


\end{graph}

\caption{The traces tree}
\end{figure}


If we denote by $H_{n}$ the sum of the values of the $n$-th row of this
latter tree, we have the following result:
 
\begin{Prop}\label{SommeTraces}  We have $H_{1}=2$, $H_{2}=1$,
$H_{3}=4$ and, for any $n\geq 3$, $H_{n}=2H_{n-1}+H_{n-3}-(-1)^n\cdot 
2$.
\end{Prop}



\begin{proof} We first prove the following statement.


\begin{Prop}\label{SommesGD} With the same notation as in the proof 
of Proposition \ref{SumEss}, we have
\[G_{3}^-=G_{4}^-=1\quad G_{n}^-=2G_{n-1}^-+G_{n-3}^-+(-1)^n\cdot
2\mbox{ (for $n\geq 5$)},\]
\[G_{3}^+=3\quad G_{4}^+=8\quad G_{n}^+=2G_{n-1}^++G_{n-3}^+-(-1)^n\cdot
2\mbox{ (for $n\geq 5$)}.\]

\end{Prop}

\begin{proof} The above relations are routinely verified for the 
first values of $n$. Let assume that these relations are true for all 
indices until
$n-1$. Recalling the relation
$G_{n}^-=G_{n-1}^+-G_{n-2}$ (see the proof of Proposition \ref{SumEss}) we
get
\begin{eqnarray*}
G_{n}^-&amp;=&amp;G_{n-1}^+ -G_{n-2}\\
&amp;=&amp;\bigl(2G_{n-2}^++G_{n-4}^+-(-1)^{n-1}\cdot 2\bigr)-\bigl(
G_{n-2}^++G_{n-2}^-\bigr)\\
&amp;=&amp;G_{n-2}^+-G_{n-2}^-+G_{n-4}^++(-1)^n\cdot 2.
\end{eqnarray*}

We thus have to verify the relation
$G_{n-2}^+-G_{n-2}^-+G_{n-4}^+=2G_{n-1}^-+G_{n-3}^-$. We write, using again 
 the relation $G_{n}^-=G_{n-1}^+-G_{n-2}$:

\begin{eqnarray*}
2G_{n-1}^-+G_{n-3}^-&amp;=&amp;2(G_{n-2}^+-G_{n-3})+(G_{n-4}^+-G_{n-5})\\
&amp;=&amp;(G_{n-2}^+-G_{n-2}^-+G_{n-4}^+)+(G_{n-2}^++G_{n-2}^--2G_{n-3}-G_{n-5})\\
&amp;=&amp;(G_{n-2}^+-G_{n-2}^-+G_{n-4}^+)+(G_{n-2}-G_{n-2}),
\end{eqnarray*}

\noindent so the desired relation for $G_{n}^-$ is verified.

We can then write
\begin{eqnarray*}
G_{n}^+&amp;=&amp; G_{n}-G_{n}^-\\
&amp;=&amp;G_{n}-\bigl(2G_{n-1}^-+G_{n-3}^-+(-1)^n\cdot 2)\\
&amp;=&amp;G_{n}-2G_{n-1}^--G_{n-3}^--(-1)^n\cdot 2\\
&amp;=&amp;G_{n}-2G_{n-1}+2G_{n-1}^+-G_{n-3}^- -(-1)^n\cdot 2\\
&amp;=&amp;G_{n-3}+2G_{n-1}^+-G_{n-3}^--(-1)^n\cdot 2\\
&amp;=&amp;2G_{n-1}^++G_{n-3}^+-(-1)^n\cdot 2,
\end{eqnarray*}
\noindent so Proposition \ref{SommesGD} is proved.

\end{proof}



We now come back to the proof of Proposition \ref{SommeTraces}. Recall
(see comments after Proposition \ref{SumEss}) that if we write 
$v_{n}=\alpha_{n}a+\beta_{n}b$ for 
the sum of the $n$-th row of the general restricted 
tree, then 
we have
\[\alpha_{0}=1\quad
\alpha_{1}=0\quad\alpha_{2}=1\quad\alpha_{3}=2
\quad\alpha_{n}=2\alpha_{n-1}+\alpha_{n-3}\mbox
{ for $n\geq 4$,}\]
\[\beta_{0}=0\quad\beta_{1}=1\quad\beta_{2}=1\quad\beta_{3}=2\quad 
\beta_{n}=2\beta_{n-1}+\beta_{n-3} 
\mbox{ for $n\geq 3$}.\]

It is clear that $\beta_{n}$ corresponds to the sum of 
all fourth coefficients of the matrices of the $n$-th 
row. The sum $\alpha_{n-1}$ is {\em not} exactly the sum of the first
coefficients of these matrices, since some $a$-coefficients in the
$(n-1)$-th row have to be counted twice. We can consider
$\alpha_{n-1}$ as the sum of the first coefficients of all matrices
which are right children. It remains, then, to evaluate the sum of
$a$-coefficients of elements of the $(n-1)$-th row which are left
children. For this, let us consider the particular case $a=1$ and $b=0$
in the general restricted tree. Let us denote by $\alpha_{n}^-$ the
sum of left children in the $n$-th row of this tree: we then have
$H_{n}=\alpha_{n-1}+\alpha_{n-1}^-+\beta_{n}$. We know by Proposition 
\ref{SommesGD} and by the fact mentioned in the begining of the
present section that, for all $n\geq 3$, we have
$\alpha_{n-1}^{-}=2\alpha_{n-2}^-+\alpha_{n-4}^-+(-1)^{n-1}\cdot 2$. We thus 
obtain the right recurrence relation for the sequence $(H_{n})_{n}$, and a
simple calculation gives the first values of this sequence.
\end{proof}


The following shows that the structure of the trace tree is more
difficult to apprehend than these of the other trees considered here.

\begin{Lemme}\label{Ilot} Let us denote by $t_{n}$ the label of the $n$-th edge 
given by a walk $(w_{n})_{n}$ in the trace tree.
\begin{itemize}
\item If $w_{n}=w_{n+1}$
(thus a $+$ sign, by Lemma \ref{GaucheGauche}), then $t_{n+2}=t_{n+1}+t_{n}$.

\item If $w_{n}=w_{n+2}$ and $w_{n+1}=w_{n+3}$ (then $w_{n}=-w_{n+1}$,
again by Lemma \ref{GaucheGauche}), then $t_{n+4}=t_{n+2}+t_{n}$.
\end{itemize}
\end{Lemme}


\begin{proof} Immediate.
\end{proof}

\begin{Lemme}\label{TraceAie}  The walks
\[+-\overbrace{+\cdots +}^{k}-\quad\mbox{and}\quad
-+\overbrace{+\cdots +}^{k}-\]
\noindent show the same sequence of labels in the trace tree, except
for the first and the last ones.

\end{Lemme}


\begin{proof} A simple calculation together with Lemma \ref{Ilot} 
show that the walk 
$+-\overbrace{+\cdots +}^{k}$ shows the successive traces $3$,
$2$, $3$, $5$,\ldots, $F_{k+3}$ and that the walk $-+\overbrace{+\cdots +}^{k}$
shows the traces  $1$, $2$, $3$, $5$,\ldots, $F_{k}$, so the 
sequence of traces are the same for the two walks, except for the
first one.

To prove that the last traces shown by the walks considered in the statement of
the Lemma are different, we need to be a little more precise. A simple
calculation shows that the last element of $\SL(2,\N)$ associated with 
$+-\overbrace{+\cdots +}^{k}$ is $\left(\begin{array}{cc}
F_{k-1}&amp;L_{k}\\ F_{k}&amp;L_{k+1}\end{array}\right)$, where $(L_{n})_{n}$ 
is the {\em Lucas sequence}, defined as $L_{1}=1$, $L_{2}=3$ and
$L_{n}=L_{n-1}+L_{n-2}$ for $n\geq 2$. In the same way, the last element of
$\SL(2,\N)$ associated with the walk  $-+\overbrace{+\cdots +}^{k}$ is 
$\left(\begin{array}{cc}
F_{k+2}&amp;F_{k}\\ F_{k+3}&amp;F_{k+1}\end{array}\right)$ (an easy recurrence
shows that, for all $k$, $F_{k-1}+L_{k+1}=F_{k+2}+F_{k+1}$, which
confirms what precedes about equality of traces). Adding the minus
sign to each of the two walks leaves to the matrix 
$\left(\begin{array}{cc}
F_{k}&amp;L_{k+1}\\ F_{k-2}&amp;L_{k-1}\end{array}\right)$ for the first walk 
and $\left(\begin{array}{cc}
F_{k+3}&amp;F_{k+1}\\ F_{k+1}&amp;F_{k-1}\end{array}\right)$ for the second.
The traces are $F_{k}+L_{k-1}$ and $F_{k-1}+F_{k+3}$, which are
different numbers for any $k$.
\end{proof}

\begin{Cor}\label{TraceTypeInfini}  The previous function
$(w_{n})_{n}\longrightarrow (t_{n})_{n}$ is not of finite type.

\end{Cor}



\subsection{Size of walks in ${\mathbf{R}}$}


\begin{Notation}  For $a$ and $b$ relatively prime, we denote by 
$\rho(a, b)$ the smallest
integer $n$ such that the $n$-th row of edges in ${\mathbf{T}}$ contains an edge 
with $a$ as
parent and $b$ as child. As established in
Proposition \ref{ShortestWay} and Proposition \ref{Containment}, 
this shortest walk shows the pairs $(r_{i},r_{i+1})$ or
$(r_{i+1},r_{i})$ for all $i$ (same notation as in the proof of
Proposition \ref{Containment}). The relatively prime integers $a$ 
and $b$ being given, any pair of the form $(r_{i},r_{i+1})$ 
(resp. $(r_{i+1},r_{i})$)
is said in {\em ascending} (resp. {\em descending}) {\em order}. When 
after $(r_{i},r_{i+1})$ comes $(r_{i},r_{i-1})$, or after $(r_{i+1},r_{i})$
comes $(r_{i-1},r_{i})$, we say that there is an {\em inversion}.

If $[n_{0},n_{1},\ldots, n_{N-1}]$ is the continued fraction expansion of
$a/b$, then let define $\gamma(a,b)$ as the total number 
of even and positive 
partial quotients $n_{i}$ with $i&lt;N-1$ (note that the last partial
quotient, $n_{N-1}$, does not count, neither $n_{0}$ in the case $a&lt;b$)
and by $\omega(a,b)$ the total number of odd partial quotients $n_{i}$ 
with $i&lt;N-1$.
We denote by 
$\omega^-(a,b)$ (resp. $\omega^+(a,b)$) 
the number of odd partial quotients $n_{i}$ with $i&lt;N-1$ 
such that the number of even partial 
quotients among $n_{i+1}$, $n_{i+2}$,\ldots, $n_{N-2}$ is odd (resp.
even).

\end{Notation}








\begin{Prop}\label{FracCont}  Let $[n_{0},\ldots, n_{N-1}]$ be the continued
fraction expansion of $a/b$, where $a$ and $b$ are
relatively prime integers. Then, we have
\[\rho(a,b)=3\cdot \left(\sum_{i&lt;N}\lfloor \frac
{n_{i}}{2}\rfloor\right)
+\omega(a,b)+\omega^\pm(a,b)-\varepsilon,\]

\noindent where

\begin{itemize}

\item if $a&lt;b$:

\[\omega^\pm(a,b)=\left\{\begin{array}{ll} \omega^+,&amp;\mbox{if $\gamma$ is
odd;}\\  
\omega^-,&amp;\mbox{if $\gamma$ is even.}\end{array}\right.
\quad\mbox{and}\quad
\varepsilon=\left\{\begin{array}{ll} 0,&amp;\mbox{if $n_{N-1}$ is
odd;}\\  
1,&amp;\mbox{if $n_{N-1}$ is even and $\gamma$ odd;}\\
2,&amp;\mbox{if $n_{N-1}$ is even and $\gamma$ even.}
\end{array}\right.\]





\item if $a&gt;b$:

\[\omega^\pm(a,b)=\left\{\begin{array}{ll} \omega^-,&amp;\mbox{if $\gamma$ is
odd;}\\  
\omega^+,&amp;\mbox{if $\gamma$ is even.}\end{array}\right.
\quad\mbox{and}\quad
\varepsilon=\left\{\begin{array}{ll} 0,&amp;\mbox{if $n_{N-1}$ is
odd;}\\  
2,&amp;\mbox{if $n_{N-1}$ is even and $\gamma$ odd;}\\
1,&amp;\mbox{if $n_{N-1}$ is even and $\gamma$ even.}
\end{array}\right.\]

\end{itemize}

\end{Prop}


\noindent Note that we do not know if there exists 
a significantly more elegant way of writing the value of
$\rho(a,b)$.

\begin{proof} We use the construction made in the proof of Lemma
\ref{Uns} and Proposition \ref{Containment}.

By a simple application of Lemma \ref{Uns}, 
the number of steps to go from the edge $(1,1)$ to the edge 
$(1,n_{N-1})$ is $3\cdot
\lfloor n_{N-1}/2\rfloor$ if $n_{N-1}$ is odd and $3\cdot \lfloor 
n_{N-1}/2\rfloor -2$ if
$n_{N-1}$ is even. In the same way, it takes $3\cdot \lfloor
n_{N-1}/2\rfloor$
steps to go from $(1,1)$ to $(n_{N-1},1)$ if $n_{N-1}$ is odd and 
$3\cdot \lfloor n_{N-1}/2\rfloor -1$ if $n_{N-1}$ is even.



From $(1,n_{N-1})$ (or $(n_{N-1},1)$) to $(a,b)$, the number of
inversions is equal to $\gamma(a,b)$. For clarity, let assume $a&lt;b$: if
$\gamma(a,b)$ is even, we thus have to attain $(1,n_{N-1})$ first, and
it
takes $3\lfloor n_{N-1}/2\rfloor-\varepsilon$ steps ($\varepsilon$
being defined as in the statement of the present Proposition); if $\gamma$ is 
odd, we have to attain $(n_{N-1},1)$, which again take 
$3\lfloor n_{N-1}/2\rfloor-\varepsilon$ steps (but maybe with a
different value for $\varepsilon$).

The summary at the end of Proposition \ref{Containment} shows that,
for all successive partial quotients after $n_{N-1}$, the number of
steps for a $n_{i}$ is given by $3\lfloor n_{i}/2\rfloor$ when $n_{i}$ 
even, $3\lfloor n_{i}/2\rfloor+1$ when $n_{i}$ 
odd and when we start at $(r_{i+2},r_{i+1})$, and  
$3\lfloor n_{i}/2\rfloor+2$ when $n_{i}$ 
odd and when we start at $(r_{i+1},r_{i+2})$.

The sum of all these terms is equal to the sum $3\sum_{i&lt;N}\lfloor
n_{i}/2\rfloor-\varepsilon$, plus the number of odd $n_{i}$s for $i&lt;N-1$ (which
corresponds to $\omega(a,b)$), plus the
number of $n_{i}$s for $i&lt;N-1$ such that the steps start at 
$(r_{i+1},r_{i+2})$, this latter number being equal to
$\omega^\pm(a,b)$ (recall that there is an inversion only for even
partial quotients).

The case $a&gt;b$ works in the same way.

\end{proof}


\begin{Cor}\label{DiffRho}  For any $a$ and $b$ relatively prime, we have 
\[|\rho(a,b)-\rho(b,a)|=
|\omega^+(a,b)-\omega^-(a,b)|\pm{\tilde \varepsilon}\]
\noindent where $|{\tilde\varepsilon}|\leq 1$.

\end{Cor}

\begin{proof} Immediate.
\end{proof}


\begin{Cor}\label{SumRho}  With the previous notation, 
we have the equality
\[\rho(a,b)+\rho(b,a)=3\left(\sum_{i&lt;N}n_{i}\right)-3.\]


\end{Cor}

\begin{proof} Denoting by $e$ the value $1$ if $n_{N-1}$ is odd
and $0$ if $n_{N-1}$ is even, we have
\begin{eqnarray*}
\rho(a,b)+\rho(b,a)&amp;=&amp;3\left(\sum_{i&lt;N}2\lfloor\frac{n_{i}}{2}\rfloor 
\right)+\omega(a,b)+\omega(b,a)+\omega^{\pm}(a,b)+\omega^{\mp}(a,b)-
\varepsilon(a,b)-\varepsilon(b,a)\\
&amp;=&amp;3\left(\sum_{i&lt;N}\frac{n_{i}}{2}-\omega(a,b)-e\right)+3\omega(a,b)-
\varepsilon(a,b)-\varepsilon(b,a)\\
&amp;=&amp;3\left(\sum_{i&lt;N}n_{i}\right)-3,
\end{eqnarray*}
\noindent and the Corollary is proved.
\end{proof}

\section{Some perspectives}

Here are some natural questions we can ask to go further in the
subject. Hopefully, we will be able to answer soon at least to the two
first following questions, for which it is quite probable that the
present paper already contains all the necessarily tools.

\begin{itemize}

\item How about replacing $(1/2,1/2)^{\otimes\N}$ by
$(p,1-p)^{\otimes\N}$~?

That is, each choice
for the sign in the expression $g_{n}=|g_{n-1}\pm g_{n-2}|$ is made by
tossing an unbalanced coin. More generally, let $P$ defines a
probability measure on $\{+,-\}^{\N}$: is it possible to give 
a reasonable and interesting assumption on
$P$ which allows to describe the average behaviour of
random Fibonacci sequences given by the law $P$?

Hopefully, the formalism introduce in the present
paper may allow to give an answer at least under an assumption of
stationnarity and type-finitness.


\item Generalized random Fibonacci sequences

Instead of considering the recurrence formula $g_{n}=|g_{n-1}\pm
g_{n-2}|$, we can consider the more general formula $g_{n}=
|\alpha g_{n-1}\pm \beta g_{n-2}|$, where $\alpha$ and $\beta$ are
real numbers. It is probable that a result similar to Theorem
\ref{Main1} could be obtained by using the tools introduced in the
previous section. With the use of the convexity inequality 
$\E(g_{n}^{1/n})\leq (\E(g_{n}))^{1/n}$ (where 
$\E$ stands for the expectation), such a result could give a lower 
bound to the value $\beta$ such that, when $\alpha=1$, almost all
random Fibonacci sequences do not increase exponentially (no
nontrivial lower bound is known at now; the best
currently known upper bound for $\beta$ is $1/\sqrt{2}$ - 
see \cite{McGowanMakover}).

The continued fraction expansion point of view
considered in the first part of the present paper may also extend to this
new case, considering another kind of continued fractions expansions, 
probably looking like
\[\alpha n_{0}+\frac{\beta}{\alpha n_{1}+\frac{\beta}{\alpha
n_{2}+\frac{\beta}{\alpha n_{3}+\cdots}}},\]
\noindent where the $n_{i}$s are integers.

Of course, one could also be interested in
more general linear recurring sequences, as $g_{n}=|\alpha
g_{n-1}\pm\beta g_{n-2}\pm\gamma g_{n-3}|$, and so forth.



\item Limits of walks in ${\mathbf{R}}$ and continued fraction expansion


Let us consider the number $1+\sqrt{2}$, whose continued fraction
expansion is $[2,2,2,\ldots]$. Its convergents are $[2]$, $[2,2]$,
$[2,2,2]$, etc. Since the continued fraction expansion of each
convergent is a suffix of the continued fraction expansion of the next
convergent, the corresponding walks in the tree ${\mathbf{R}}$ are included one
into the other. It is then possible to talk about a pair of infinite
walks 
corresponding to $1+\sqrt{2}$ (the union of the two walks giving the
set of all pairs of the form 
$(p_{n},q_{n})$ and $(q_{n},p_{n})$, where
$p_{n}/q_{n}$ are the convergents to $1+\sqrt{2}$). 
Let us consider now the number
$\sqrt{2}=[1,2,2,2,\ldots]$. Its convergents are $[1]$, $[1,2]$,
$[1,2,2]$, etc., so the suffix property is not true anymore. It
remains that the finite walks in ${\mathbf{R}}$ given by these convergents are
linked together. Indeed, it is easily proved that, apart for a final
``branch'' which is identical for all convergents, the pair of walks are the
same as those for the convergents of $1+\sqrt{2}$. Thus, it seems that
there is also something like a limit of the pair of walks for the convergents 
of $\sqrt{2}$. An interesting fact is that this limit may be equal to 
the limit walks for $1+\sqrt{2}$, that is, this point of view
identifies equivalent numbers (in the sens of continued fractions, two
numbers are equivalents iff they have the same partial quotients apart
for the first ones).

These considerations extends to any quadratic number, that is, thanks 
to Lagrange's theorem, numbers whose continued fraction expansion is
periodic (we get $n$ pairs of infinite walks for a number whose partial
quotients are perioodic with period $n$). Is it possible to get an
interesting generalization of this, at least for some numbers (for
example: numbers with bounded partial quotients)?


\item With the roots of unity

Another possible generalization of random Fibonacci sequences is to
choose an integer $p\geq 2$ and define a random Fibonacci sequence by 
$g_{n}=g_{n-1}+(e^{2i\pi/p})^{Z(\omega)}\cdot g_{n-2}$ (or 
$g_{n}=|g_{n-1}+(e^{2i\pi/p})^{Z(\omega)}\cdot g_{n-2}|$, or other
formulas of the same kind), where $Z$ is a random variable taking
values in $\{0,\ldots p-1\}$. We then get $p$-ary trees instead of
binary trees. Are there interesting facts to say about these sequences?






\end{itemize}



We finish with a heuristic link between the trees ${\mathbf{R}}$ and ${\mathbf{T}}$ (a
rigorous proof of it will be made in a forthcoming paper). Let us
denote by $\tau$ the growth rate of almost all random Fibonacci
sequence (we know, thanks to Viswanath \cite{Viswanath}, that $\tau\approx
1.13198824$), and by $\rho$ the corresponding constant for walks in
${\mathbf{R}}$ instead of ${\mathbf{T}}$ (we do not prove here that such a $\rho$ exists). 
 
Let us write, in a very crude manner, a typical random Fibonacci sequence 
as $g_{n}=\tau^n$ for all $n$. We denote by $\gamma_{n}$ the node in
${\mathbf{R}}$ corresponding to the node $g_{n}$ in ${\mathbf{T}}$ by projection, and by
$\lambda(n)$ the rank of the row of ${\mathbf{R}}$ to which $\gamma_{n}$ belongs.
The supposed existence of $\rho$ implies that, again in a heuristic 
way,  $\tau^n=\rho^{\lambda(n)}$.

At the time $n$, the probability that the projection will have to get 
back two rows before in ${\mathbf{R}}$ is given by the ratio between the number
of ``lacking'' left children in $\rho_{n}$ and the total number of
children of $\rho_{n}$ in the complete binary tree. This ratio is
equal to $F_{n-2}/2F_{n}$,which is asymptotically equal to $1/2\varphi^2$.
Therefore, we have (again in a heuristic way):

\[\lambda(n+1)=\left(1-\frac{1}{2\varphi^2}\right)\cdot(\lambda(n)+1) 
+\frac{1}{2\varphi^2}\cdot(\lambda(n)-2).\]

Simplifying the latter equality gives 
$\lambda(n+1)=\lambda(n)+1-3/2\varphi^2$, so

\[\lambda(n)=\left(1-\frac{3}{2\varphi^2}\right)\cdot n.\]

Putting this in the relation $\tau^n=\rho^{\lambda(n)}$ then gives
\[\tau=\rho^{1-3/2\varphi^2}.\]


In particular, the knowledge of an
analytic expression of $\tau$ could be derived from the knowledge of
an analytic expression of $\rho$. Moreover, thanks to  classical
theorem of
Gelfond-Schneider, the previous equality  implies that
$\rho$ and $\tau$ cannot be both algebraic irrational numbers.

\section{Acknowledgments}

The author is grateful to Thierry de la Rue, Florent Hivert and 
\'Elise Janvresse
from Universit\'e de Rouen, and Anne Broise and Thierry Bousch from
Universit\'e Paris-Sud, for fruitful discussions.


\begin{thebibliography}{99}

\bibitem{AST} J.-P. Allouche, K. Scheicher and R. Tichy, 
Regular maps in generalized number systems, {\it 
Math. Slovaca} {\bf 50} (2000), 41--58. 

\bibitem{AS1} J.-P. Allouche and J. Shallit, The ring of $k$-regular
sequences, {\it Theor. Comput. Sci.} {\bf 98} (1992), 163--197.

\bibitem{AS2} J.-P. Allouche and J. Shallit, The ring of $k$-regular
sequences, II {\it Theor. Comput. Sci.} {\bf 307} (2003), 3--29.

\bibitem{EBT} \'E. Janvresse, B. Rittaud and T. de la Rue, How fast do
random Fibonacci sequences grow?,
\href{http://fr.arxiv.org/abs/math.PR/0611860}{\tt http://fr.arxiv.org/abs/math.PR/0611860}

\bibitem{McGowanMakover} J. McGowan and E. Makover, 
An elementary proof that random Fibonacci sequences grow
exponentially, {\it J. Number Theory} {\bf 121} (2006), 40--44.

\bibitem{Viswanath} D. Viswanath, Random Fibonacci
sequences and the number 1.13198824\ldots, {\it Math.
Comp.} {\bf 69} (2000),  1131--1155.

\bibitem{EIT} The On-Line Encyclopedia of Integer Sequences, \hfil\break
\href{http://www.research.att.com/~njas/}{\tt {http://www.research.att.com/$\sim$njas/}}


\end{thebibliography}




\bigskip
\hrule
\bigskip


\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 11A55; Secondary 15A52, 05C05, 15A35.

\noindent \emph{Keywords: } 
binary tree, random Fibonacci tree, linear
recurring sequence, random Fibonacci sequence, continued fraction.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A001764},
\seqnum{A008998}, and
\seqnum{A083404}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 21 2006;
revised version received  January 18 2007.
Published in {\it Journal of Integer Sequences}, January 19 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


</pre></body></html>