\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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#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},&\mbox{if $k\equiv 1$ or $2$ (mod $3$);}\\ g_{k-1}-g_{k-2},&\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},&\mbox{if $k\equiv 0$ or $2$ (mod $3$);}\\ g_{k-1}-g_{k-2},&\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>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>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>m'\Longrightarrow n\geq n'$ and $n>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>m'$ implies $n\geq n'$ and $n>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'|>m$ implies $|n-n'|\geq n$ and that $|n-n'|>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'|>m$ and wish to prove that $|n-n'|\geq n$. Since $m$ and $m'$ are integers, the inequality $|m-m'|>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>a$ since, apart for nodes in the top of the tree, we have $b=a+z$ and $z> 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>z$, so $b=a-z3$, $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}&=&G^-_{n}+S(\sigma^-_{n})+S(\sigma^+_{n})\\ &=&(G^+_{n-1}-G_{n-2})+(G^-_{n-1}+G^+_{n-2})+(G^+_{n-1}+G_{n-2})\\ &=&2G^+_{n-1}+G^-_{n-1}+G^+_{n-2}\\ &=&2G_{n-1}+G^+_{n-2}-G^-_{n-1}\\ &=&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 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}&=&s(s^{n}(\rho_{2}))\\ &=&s\left(\sum_{m=0}^{k}c_{n,m} \nu_{n+2-3m}\right)\\ &=&s( c_{n,k} \nu_{2} )+ \sum_{m=0}^{k-1} c_{n,m} \cdot(\nu_{n-3(m-1)}+\nu_{n-3m})\\ &=&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}\\ &=&(c_{n,k}+c_{n,k-1})\nu_{3}+\sum_{m=-1}^{k-2}(c_{n,m+1}+c_{n,m})\nu_{n-3m}\\ &=&c_{n+1,k}\nu_{3}+ \sum_{m=-1}^{k-2}c_{n+1,m+1}\nu_{n-3m}\\ &=&\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}|<1$ and exponential with ratio $z^{1/2}$ if $|zx^{-2}|>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)}\\ &=&\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})\\ &=& \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|<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}} &=&\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}\\ &=&{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}} &=& \frac{\sum_{m=0}^{k}{n+1\choose m}(\alpha^{-3})^m}{\sum_{m=0}^{k} {n\choose m}(\alpha^{-3})^m}\\ &=&\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}\\ &=&1+\frac{\sum_{m=0}^{k}{n\choose m-1}(\alpha^{-3})^m}{\sum_{m=0}^{k} {n\choose m}(\alpha^{-3})^m}\\ &=&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}\\ &=&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}\\ &=&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 $k0$ 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>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>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>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 j0$, 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 $im'$ then $n\geq n'$ and if $n>n'$ then $m\geq m'$. In particular, if $m>m'$ then $m+n>m'+n'$ and $M$ has no left child (take $a=b=1$ and use Lemma \ref{Ordre}). For the same reason, if $n>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&1 \\ -1& 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&1 \\ 1& 1\end{array}\right)$, where $\gamma_{0}=0$ or $1$, $\delta_{i}>0$ for all $i$ between $0$ and $k-1$ and $\delta_{k}\geq 0$. The matrix $\left(\begin{array}{cc} 0&1 \\ 1& 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&=&(G^{\gamma_{0}}D^{\delta_{0}} GD^{\delta_{1}}\cdots GD^{\delta_{k-1}}GD^{\delta_{k}}\cdot D)^T\\ &=&D\cdot D^{\delta_{k}}{}^tGD^{\delta_{k-1}}{}^tG\cdots D^{\delta_{1}}{}^tGD^{\delta_{0}}{}^tG^{\gamma_{0}}\\ &=&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}}\\ &=&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}^-&=&d_{n-1}^+-d_{n-1}^-\\ &=&(g_{n-2}^-+d_{n-2}^-)-(g_{n-2}^++d_{n-2}^+)\\ &=&-e_{n-2}-(d_{n-2}^+-d_{n-2}^-)\\ &=&-e_{n-2}-(g_{n-1}^+-g_{n-1}^-)\\ &=&-(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}^-&=&G_{n-1}^+ -G_{n-2}\\ &=&\bigl(2G_{n-2}^++G_{n-4}^+-(-1)^{n-1}\cdot 2\bigr)-\bigl( G_{n-2}^++G_{n-2}^-\bigr)\\ &=&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}^-&=&2(G_{n-2}^+-G_{n-3})+(G_{n-4}^+-G_{n-5})\\ &=&(G_{n-2}^+-G_{n-2}^-+G_{n-4}^+)+(G_{n-2}^++G_{n-2}^--2G_{n-3}-G_{n-5})\\ &=&(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}^+&=& G_{n}-G_{n}^-\\ &=&G_{n}-\bigl(2G_{n-1}^-+G_{n-3}^-+(-1)^n\cdot 2)\\ &=&G_{n}-2G_{n-1}^--G_{n-3}^--(-1)^n\cdot 2\\ &=&G_{n}-2G_{n-1}+2G_{n-1}^+-G_{n-3}^- -(-1)^n\cdot 2\\ &=&G_{n-3}+2G_{n-1}^+-G_{n-3}^--(-1)^n\cdot 2\\ &=&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}&L_{k}\\ F_{k}&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}&F_{k}\\ F_{k+3}&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}&L_{k+1}\\ F_{k-2}&L_{k-1}\end{array}\right)$ for the first walk and $\left(\begin{array}{cc} F_{k+3}&F_{k+1}\\ F_{k+1}&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 $ib$: \[\omega^\pm(a,b)=\left\{\begin{array}{ll} \omega^-,&\mbox{if $\gamma$ is odd;}\\ \omega^+,&\mbox{if $\gamma$ is even.}\end{array}\right. \quad\mbox{and}\quad \varepsilon=\left\{\begin{array}{ll} 0,&\mbox{if $n_{N-1}$ is odd;}\\ 2,&\mbox{if $n_{N-1}$ is even and $\gamma$ odd;}\\ 1,&\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 $ab$ 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