1

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?)

jamaicanworm
  • 4,494
  • What do you mean by to solve it? To find the limit if it exists? To find a closed form for the $n$-th term? – mathcounterexamples.net Feb 29 '16 at 20:05
  • @mathcounterexamples.net Both! I want to know the closed form, then use that to find the limit (which I suspect is 1). – jamaicanworm Feb 29 '16 at 20:07
  • 3
    In general it's very hard to find closed form expressions for nonlinear recurrence relations. As for finding the limit, try to first prove the limit exists, and then argue about what this limit must be. – Wojowu Feb 29 '16 at 20:22
  • Limit (if it exists, may depend on $a_0$) is a zero of $u = a u^2 + c$, i.e., $u = (1 \pm \sqrt{1 - 4 a c})/(2 a)$ – vonbrand Feb 29 '16 at 20:25
  • 1
    Generally, such quadratic recurrence relations don't have a nice closed form. Some of them do (for example, $a_{n+1}=2a_n^2\pm1$), but yours does not. – Ivan Neretin Feb 29 '16 at 22:01

2 Answers2

2

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

mathcounterexamples.net
  • 70,018
1

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.

Nate
  • 11,206