lamplighter group - Growth from Fibonacci tree Let $G_1 = \mathbb{Z}_2 \wr \mathbb{Z}$ be the lamplighter group.
I'm looking at a proof that it's growth rate is $\varphi = \frac{1+\sqrt{5}}{2}$ using a Fibonacci tree, as explained in this paper
The First Step is to prove that $gr(G_1) \geq \varphi$. This is ok for me. Let $x=(m,\eta) \in G_1$ with $m\in\mathbb{Z}$ the the position of lampligher, and $\eta\in\{0,1\}^\mathbb{Z}$ the states of the "lamps". Let $\text{flag}_R$ be the "first lit lamps" from the right, i.e.
$$ \text{flag}_R = \sup\{ k \geq 0, \eta(k)=1\}$$
You build a subgraph of the Cayley graph of $G_1$, as follow. The vertices consist of states $x=(m,\eta)$ for which $m\geq\text{flag}_R$ and $\eta(k)=0$ for all $k<0$. You start with the root $\Theta$ being the initial state ($m=0$, $\eta=0^\mathbb{Z}$) and for each vertex :


*

*if $m=\text{flag}_R$, then the vertex $(m,\eta)$ has one single child : $(m+1,\eta)$,

*if $m>\text{flag}_R$, then the vertex $(m,\eta)$ has two children : $(m+1,\eta)$ and $(m,\eta\oplus 1_m)$
Looking at the variable $d = m-\text{flag}_R$, building the tree it's easy to see that this form a Fibonacci tree : Each vertex has one single grandchildren with $d=0$, and each vertex has one single child with $d\neq 0$, hence the $n^\text{th}$ level has $l_n$ vertices with
$$ l_n = l_{n-1}+l_{n-2}$$
(we also need to prove that we never encounter twice the same vertex, this is ok because we never "walkback" from position, we can only go from $m$ to $m+1$)
Since the number of vertices at distance $n$ from the root of the Fibonacci tree is asymptotically $O(\varphi^n)$, this concludes that $gr(G_1)\geq \varphi$ 
To conclude that this is in fact an equality, the authors state that 

From this, it is not hard to see that an upper bound for the number of vertices at distance $n$ from $\Theta$ in the Cayley graph of $G_1$ is a constant time $\sum_{k\leq n}\varphi^k$, which, again, is just asymptotically a constant time $\varphi^n$. Hence $gr(G_1)=\varphi$

Is this because you can upper bound the number of vertices in $G_1$ (after $n$ steps) seeing that each one must belong to at least one of the Fibonacci trees starting at state $(-k, 0^\mathbb{Z})$, with $k=0,\ldots,n$ ? I'm think I have the right feeling, but I can't write the math properly. Any help is welcome.
 A: Lemma: The number of 0-1 strings of length $n$ avoiding $'00'$ is at most $C\varphi^n$.
Proof: Let $\Sigma_n$ be the set of such strings. Note $\Sigma_n = \{01c : c \in \Sigma_{n-2}\}\cup\{1c : c \in \Sigma_{n-1}\}$, so $|\Sigma_n| \le |\Sigma_{n-1}|+|\Sigma_{n-2}|$, yielding a fibonacci recurrence. $\square$
.
Main Problem: Let $f$ correspond to flip, $R$ to right, and $L$ to left. Note all elements of $G_1$ that can be achieved in at most $n$ steps can be written as a sequence of $f$'s, $L$'s, and $R$'s such that (1) there are no two $f$'s in a row, and (2) there is no $L$ appearing after an $R$ (i.e., we can WLOG that we go left for a bit and then only go right or flip from then on). For $0 \le k \le n$, we may consider the set of such sequences that don't go left after the $k^{th}$ step. Since the first $k$ steps comprise $f$'s and $L$'s without two $f$'s in a row, there are, by the Lemma, at most $C\varphi^k$ possibilities for the first $k$ steps, and then since the last $n-k$ steps are comprised of only $R$'s and $f$'s with no two $f$'s in a row, there are at most $C\varphi^{n-k}$ possibilities for the last $n-k$ steps. This gives me $\sum_{k=0}^n C^2\varphi^k\varphi^{n-k} = C^2n\varphi^n$. Although the authors say $C\varphi^n$, my upper bound $C^2n\varphi^n$ still gives $\varphi$ as an upper bound for the growth rate.
