The last few days I am trying my best to understand a part of a proof from [these](https://www.win.tue.nl/%7Erhofstad/percolation_randomgraphs_rev.pdf) lecture notes on page 14:


[Picture of the relevant part](https://i.stack.imgur.com/0297Xl.png)


The setting is percolation on a regular tree with degree $r$, $C\_{BP}(x)$ denotes the cluster of $x$ and $h(\cdot)$ is the distance of the vertex from the origin. It is clear to me why $\theta\_n$ satisfies the recursion (1.57).


However, I was not able to show that (1.57) together with $p\_c=1/(r-1)$ implies that $\theta\_n=(C\_\rho+o(1))/n$ for some
constant $C\_\rho>0$.


After some looking around I have also found this problem as an exercise with the hint to consider $v\_n=1/\theta\_n$ and performing induction on $n$. Unfortunately I am really stuck and don't see what to do. Maybe someone can help me. Is there hope for an explicit formula for $\theta\_n$ or $v\_n$? Thank's a lot for your help and time.



Deriving an asymptotic statement from a recursion
$\newcommand{\ep}{\varepsilon}$Let
\begin{equation\*}
 x\_n:=\theta\_n,\quad s:=r-1>1,\quad b:=\frac{s-1}{2s}>0,
\end{equation\*}
\begin{equation\*}
 f(x):=1-(1-x/s)^s,
\end{equation\*}
so that
\begin{equation\*}
 x\_n=f(x\_{n-1}) 
\end{equation\*}
for natural $n$, with $x\_0\in[0,1]$. Without loss of generality, $x\_0\in(0,1]$.


We have $f'(x)=(1-x/s)^{s-1}<1$ for $x\in(0,1]$ and hence $f(x)<x$ for $x\in(0,1]$, so that $x\_n$ is decreasing to some limit $x\_\infty=f(x\_\infty)\in[0,1]$. Therefore and because $f(x)<x$ for $x\in(0,1]$, we have $x\_\infty=0$, so that $x\_n\downarrow0$ (as $n\to\infty$).


Next, $f(x)=x-(b+o(1))x^2$ as $x\downarrow0$. So,
\begin{equation\*}
 x\_n=x\_{n-1}-a\_n x\_{n-1}^2
\end{equation\*}
for some $a\_n\to b$ and all natural $n$. Letting now
\begin{equation\*}
 c\_n:=nx\_n,
\end{equation\*}
we have
\begin{equation\*}
 c\_n=\frac n{n-1}\,c\_{n-1}-\frac{b\_n}n\,c\_{n-1}^2 \tag{1}
\end{equation\*}
for some
\begin{equation\*}
 b\_n\to b. \tag{2}
\end{equation\*}


Since $c\_n/n=x\_n\to0$, by (1) and (2), we get the crucial conclusion that  

\begin{equation\*}
 \frac{c\_n}{c\_{n-1}}\to1. \tag{2.5}
\end{equation\*}


Take now any $h\in(0,1)$. Informally, we are going to show that the sequence $(c\_{n-1})$ is mainly confined between the left "moving barrier" $(c^{-h}\_n)$ and the right "moving barrier" $(c^h\_n)$, where
\begin{equation\*}
 c^{-h}\_n:=\frac n{n-1}\,\frac{1-h}{b\_n},\quad c^h\_n:=\frac n{n-1}\,\frac{1+h}{b\_n}. 
\end{equation\*}
Moreover, by (2.5) and (2), the jumps of the sequence $(c\_{n-1})$ from between these two moving barriers
to the left or right of both of these moving barriers will be of negligible magnitudes.


Indeed, if, for some $n\ge3$, we have
\begin{equation\*}
 c\_{n-1}\le c^{-h}\_n, \tag{3}
\end{equation\*}
then, by (1),  

\begin{equation\*}
 \frac{c\_n}{c\_{n-1}}\ge1+\frac h{n-1}>1. \tag{4}
\end{equation\*}
Therefore and because $\prod\_{j=2}^\infty(1+\frac h{j-1})=\infty$, we will have $c\_n\to\infty$ if (3) holds for all natural $k\ge n$, in place of $n$, that is, if $c\_{k-1}\le c^{-h}\_k$ for all natural $k\ge n$. However, in view of (2), $c^{-h}\_k\to\frac{1-h}b<\infty$ as $k\to\infty$. So, (3) cannot hold for all natural $k\ge n$, in place of $n$. So,
there will be some natural $m=m\_n\ge n$ such that
\begin{equation\*}
 c\_{n-1}\le c^{-h}\_n,\dots,c\_{m-1}\le c^{-h}\_m,\ c\_m>c^{-h}\_{m+1}
\end{equation\*}
and
\begin{equation\*}
 c\_{n-1}<\cdots<c\_{m-1}<c\_m.
\end{equation\*}
Informally, if $(c\_{n-1})$ ventures to the left of the (left) moving barrier $(c^{-h}\_n)$, it is returned, in a finite number of steps and in a monotonic manner, to the right of the moving barrier $(c^{-h}\_n)$.


On the other hand, similarly, if, for some $n\ge3$, we have
\begin{equation\*}
 c\_{n-1}\ge c^h\_n, \tag{3a}
\end{equation\*}
then, by (1),  

\begin{equation\*}
 \frac{c\_n}{c\_{n-1}}\le1-\frac h{n-1}<1. \tag{4a}
\end{equation\*}
Therefore, in view of (2) and because $\prod\_{j=2}^\infty(1-\frac h{j-1})=0$, there will be some natural $k=k\_n\ge n$ such that
\begin{equation\*}
 c\_{n-1}\ge c^h\_n,\dots,c\_{k-1}\ge c^h\_k,\ c\_k<c^h\_{k+1}
\end{equation\*}
and
\begin{equation\*}
 c\_{n-1}>\cdots>c\_{k-1}>c\_k.
\end{equation\*}
Informally, if $(c\_{n-1})$ ventures to the right of the (right) moving barrier $(c^h\_n)$, it is returned, in a finite number of steps and in a monotonic manner, to the left of the moving barrier $(c^h\_n)$.


Recalling now (2.5) and (2), we conclude that, for any $h\in(0,1)$,
\begin{equation\*}
 \frac{1-h}b\le\liminf\_n c\_n\le\limsup\_n c\_n\le\frac{1+h}b;
\end{equation\*}
that is, $c\_n\to1/b$; that is, $\theta\_n=x\_n\sim1/(nb)$, as desired.


