Given nonlinear recurrence relation : $b_n=(\frac{1}{2}b_{n-1}+\frac{1}{2})^2$, then evaluate $\lim_{n\to\infty} (b_n)^{2n}$

Question

I encounter the following problem: Given nonlinear recurrence relation : $b_n=(\frac{1}{2}b_{n-1}+\frac{1}{2})^2$ with $b_0=\frac{1}{2}$, we want to evaluate the $\lim_{n\to\infty} (b_n)^{2n}$.

Firstly, I use MATLAB to verify this numerically, and the result should be $e^{-8}$.

I know it is not easy to find a close form of a nonlinear recurrence relation(here it is a quadratic map) in general. Here, we can see that $\lim_{n\to\infty}b_n=1$. Indeed, assume $\lim_{n\to\infty}b_n=L$, and substitute it into the recurrence relation. We will get:$L=(\frac{1}{2}L+\frac{1}{2})^2$, and the solution is $L=1$. Although maybe we cannot find the exact form of $b_n$, is it possible for us to find how fast it converges to $1$?

Thanks for any hint.

Answer 1

$$b_n=\left(\frac{1}{2}b_{n-1}+\frac{1}{2}\right)^2$$

Given that $b_n\to1$, we consider $\gamma_n=\frac{b_n-1}{2}$, and this leads us to:

$$\gamma_{n+1}=\gamma_{n}+\frac{1}{2}\gamma_{n}^2$$

As a heuristic, we try $\gamma_n\sim An^{-\beta}$ to see what behaviour to expect:

$$A(n+1)^{-\beta}\approx An^{-\beta}+\frac{1}{2}A^2n^{-2\beta}$$

$$\implies\left(1+\frac{1}{n}\right)^{-\beta}\approx1+\frac{-\beta}{n}\approx 1+\frac{A}{2n^{\beta}}$$

Matching, we choose $\beta=1,A=-2$, and so we suspect that $\gamma_n\approx\frac{-2}{n}$. We thus set $f_n=\frac{-2}{\gamma_n}\to\infty$:

$$f_{n+1}=\frac{f_n^2}{f_n-1}=f_n+1+\frac{1}{f_n-1}=f_n+1+o(1)\implies f_n=n+o(n)$$

We thus deduce:

• $\gamma_n=\frac{-2}{n+o(n)}$
• $b_n=1-\frac{4}{n+o(n)}$
• $\log\left(b_n^{2n}\right)=2n\log\left(1-\frac{4}{n+o(n)}\right)=(2n)\left(\frac{-4}{n+o(n)}+o\left(\frac{-4}{n+o(n)}\right)\right)=-8+o(1)$

Thus, $b_n^{2n}\to \exp(-8)$ as $n\to\infty$.