Solving recurrence relations of the form $a_{n} = b a_{n-1}^2 + c$

Question

I have a recurrence relation of the form $a_{n} = b a_{n-1}^2 + c$, where $c \neq 0$.

Specifically, mine is $a_{n} = \frac{1}{2} a_{n-1}^2 + \frac{1}{2}$, with $a_0 = \frac{1}{2}$.

How are these solved? (What is the closed form, and does it have a limit?)

Answer 1

I don't know how to find a closed form.

You can prove that $(a_n)$ converge to $1$ as:

1. $a_n$ can be proved to be less than $1$ by induction: $$a_{n+1}-1=\frac{1}{2}a_n^2-\frac{1}{2}=\frac{1}{2}(a_n-1)(a_n+1)<0$$
2. $(a_n)$ is increasing also by induction $$a_{n+1}-a_n =\frac{1}{2}(a_n^2-2a_n+1)=\frac{1}{2}(a_n-1)^2 >0$$

Therefore $(a_n)$ converge and the limit $l$ is one as it satisfies $$l=\frac{1}{2}l^2+\frac{1}{2}.$$

Answer 2

Not really an answer to your question, but here's bit of general theory: for a recursion of the form $a_n = f(a_{n-1})$ for some smooth function $f$ and a point $x$ satisfying $f(x) = x$ we can ask if for initial values $a_0$ near $x$ whether $a_n \to x$ as $n \to \infty$.

It turns out that this sort of local dynamics is determined by the derivative of $f$ at $x$. In particular if $|f'(x)| < 1$ there exists a neighborhood $N$ around $x$ such that if we take $a_0 \in N$ then $a_n \to x$ as $n \to \infty$ and we say $x$ is an attractive or stable fixed point.

On the other hand if $|f'(x)| > 1$ then there is a neighborhood $N$ of $x$ such that for every $a_0 \in N-\{x\}$ there is some $n$ such that $a_n \not\in N$. In this case we say that $x$ is a repelling or unstable fixed point.

Now in the example you have where $f(x) = \frac{x^2+1}{2}$ we have that $f(1) = 1$. Such a fixed point is called semistable, and you can verify that if $a_0$ is taken to be positive and less than $1$ then the sequence converges to $1$, whereas if $a_0$ is taken to be more than $1$ the sequence goes to infinity.

This sort of qualitative description of the dynamics can be extremely useful, but I feel I should end with the caveat that it only works locally. Even in your main example, if you take $a_0$ to be sufficiently negative then something "global" occurs and you again end up diverging to (positive) infinity.