5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Winther You're right! The limit value seems to be small, but doesn't converge to 0. Let me edit the problem. $\endgroup$ – Syoung Jan 2 '17 at 17:43
  • 1
    $\begingroup$ One possible approach: Let $c_n = \frac{b_n-1}{2}$ then $c_{n+1} = c_n + \frac{1}{2}c_n^2$ so if the limit $\lim_{n\to\infty} nc_n = c$ exists then by Stolz–Cesàro we have $$c = \lim_{n\to\infty} n c_n = \lim_{n\to\infty} \frac{c_{n+1}-c_n}{\frac{1}{n+1} - \frac{1}{n}} = -\lim_{n\to\infty} \frac{[nc_n]^2}{2} = -\frac{c^2}{2}$$ giving $c=-2$ and $b_n^{2n} = \lim_{n\to\infty}(1 + 2c_n)^{2n} = e^{-8}$ follows. You need to show that $nc_n$ converges though. $\endgroup$ – Winther Jan 2 '17 at 18:20
  • $\begingroup$ @Winther Thanks so much! $\endgroup$ – Syoung Jan 2 '17 at 19:31
5
$\begingroup$

$$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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.