Deriving an asymptotic statement from a recursion The last few days I am trying my best to understand a part of a proof from these lecture notes on page 14:
Picture of the relevant part
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.
 A: $\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.
A: $\quad$Restate what was said in my comments. Using a computer to view my answer will be better.
Theorem. Let $A>0,\alpha>0$ and $f(x)$ be the function satisfying the following condition
$$f(x)=x-Ax^{1+\alpha}+Bx^{1+2\alpha}+O\left(x^{1+3\alpha}\right),\ x\to 0.$$
If $a_{n+1}=f(a_n)$ and the sequence $(a_n)_{n\geqslant 1}$ is monotone decreasing to zero, then
$$a_n=\frac{1}{C^{\beta}n^{\beta}}+\left(B-\frac{(\alpha+1)A^2}{2}\right)\frac{\log n}{C^{2+\beta}n^{1+\beta}}+O\left(n^{-1-\beta}\right)$$
holds as $n\to \infty$, where $C=A\alpha,\beta=\frac{1}{\alpha}$.
Proof. Putting $b_n=a_n^{-\alpha}$, we have $b_n\to +\infty$ and
\begin{align*}
  b_{k+1}& =\frac{1}{a_{k+1}^{\alpha}}=b_k\left(\frac{a_{k+1}}{a_k}\right)^{-\alpha}\\
  & =b_k\left(1-Aa_k^{\alpha}+Ba_k^{2\alpha}+O\left(a_k^{3\alpha}\right)\right)^{-\alpha}\\
  & =b_k\left(1-\frac{A}{b_k}+\frac{B}{b_k^2}+O\left(b_k^{-3}\right)\right)^{-\alpha}\\
  & =b_k+C+\frac{D}{b_k}+O\left(b_k^{-2}\right),\tag{1}
\end{align*}
where $D=\frac{\alpha(\alpha+1)}{2}A^2-B\alpha$.
The O'Stolz Theorem shows that
$$\lim_{n\to \infty}\frac{b_n}{n}=\lim_{n\to \infty}(b_{n+1}-b_n)=C.$$
Sum the formula (1) from $k=1$ to $k=n-1$ and get
\begin{align*}
  b_n& =b_1+C(n-1)+\sum_{k=1}^{n-1}\frac{D+o(1)}{Ck}+O\left(\sum_{k=1}^n\frac{1}{k^2}\right)\\
  & =Cn+\frac{D+o(1)}{C}\log n+O(1)\\
  & =Cn\left(1+O\left(\frac{\log n}{n}\right)\right).
\end{align*}
Sum again and we get
\begin{align*}
  b_n& =b_1+C(n-1)+\sum_{k=1}^{n-1}\frac{D+O\left(\frac{\log k}{k}\right)}{Ck}+O\left(1\right)\\
  & =Cn+\frac{D}{C}\log n+O(1).
\end{align*}
The proof completes with the substitution $a_n=b_n^{-\beta}$.$\quad\square$
$\quad$Now $f(x)=x-\frac{r-2}{2r-2}x^2+O(x^3)$, derived from
$$1-\theta_{n+1}=\left(1-\frac{\theta_n}{r-1}\right)^{r-1},$$
implies that
$$a_n\sim \frac{2r-2}{r-2}\cdot\frac{1}{n},n\to \infty.$$
