Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've run across the recurrence $a_{n+1} = (a_n)^2 + 1$ in the past. Unfortunately, the referrence escapes me. However, my impression was that recurrences involving the product of previous terms (such as $a_{n+1} = (a_n)(a_{n-1})$) are difficult to solve. I'm wondering what is known for this very general problem.

(1) Is there a known way to solve recurrences involving the product of previous terms? Or, what is known about these?

(2) What are these recurrences called? Do they have a general name (such as non-linear recurrences)?

(3) Where can I find more literature on the subject?

(4) Who are some experts that have dealt with this?

share|cite|improve this question
So, quadratic maps? – J. M. Nov 30 '10 at 14:39
In general though, even simple recurrences like the logistic map possess no closed-form solutions. – J. M. Nov 30 '10 at 14:41
@J.M.: Yes, Quadratic maps! I've been rewriting $a_{n+1}$ as $a_{n^2}$. I guess this is far from novel, though. – Matt Groff Nov 30 '10 at 14:50
After answering this question, I was searching to find similar questions. I came across your question and thought that perhaps that question was what you were remembering. – robjohn May 4 '14 at 18:56
up vote 13 down vote accepted

$a_{n+1} = a_n a_{n-1}$ happens to be quite easy to solve: if $b_n = \log a_n$ then $b_n$ satisfies the Fibonacci recurrence.

The only recurrences of the form $a_{n+1} = a_n^2 + c$ that have anything like a closed form solution occur when $c = 0$ (obvious) and when $c = -2$ (where the solution is given by $a_n = 2 \cos 2^n \theta$ where $\theta$ is determined by $a_0$). For all other values of $c$ you get very complicated behavior, and the situation for more general nonlinear recurrences is even worse. People study questions like these in dynamical systems and related areas; one keyword you might use to start your exploration is Julia set.

Like many other classes of sufficiently general problems in mathematics, the problem is hopelessly complicated in general and people study interesting special cases.

share|cite|improve this answer

Sometime ago I considered the sequence of fractions defined by $a_1 = 1/2$, $a_{n+1} = (a_n^2 + 1)/2$, in some probabilistic context; see OEIS seqence A167424 . This sequence is closely related to the one defined by $a_1 = 1/2$, $a_{n+1}=a_n-a_n^2$, see OEIS sequence A076628, whose asymptotics as $n \to \infty$ was analyzed here.

share|cite|improve this answer

You may want to take a look at Kelley and Peterson's textbook [1]. The problem you are looking at here is a recurrence relation as you have stated. You also hear them called difference equations. If you are familiar with differential equations, these difference equations are the discrete analog of differential equations [2].

Kelley and Peterson go very in depth with solving different types of difference equations. They give a nice overview of several different methods.

I hope this helps you! If you have any other questions, feel free to email me or contact me through my blog

[1] Kelley, W. & Peterson, A. (2001). Difference Equations: An Introduction with Applications (2nd Ed.). San Diego, CA: Academic Press.

[2] Weisstein, Eric W. "Recurrence Equation." From MathWorld--A Wolfram Web Resource.

share|cite|improve this answer

If we have a sequence $a_{n+1} = f(a_n, ..., a_{n-k})$ where $f$ is a quadratic polynomial in $k$ variables, then we can use this recurrence relation to write down a "simplified" recurrence relation:

$a_{n+1} = g(a_{n-k})$ where $g$ is a polynomial of even degree.

Define a new sequence $b_j = a_{(k+1) \cdot j}$.

Then $b_{j+1} = a_{kj + k + j + 1} = g(a_{(k+1)j}) = g(b_j)$.

Notice that if $a_n$ converges, then so does $b_n$ and $\lim a_n = \lim b_n$. Denote $\lim b_n$ by $b$.

As $g$ is continuous,

$\lim_{n \rightarrow \infty} b_n = \lim_{n \rightarrow \infty} g(b_{n+1}) = g( \lim_{n \rightarrow \infty} b_n )$

Thus, $g(b) = b$, so the limit of the sequence $a_n$ must be one of the fixed points of $g$.

To find the fixed points of $g(x)$, one must find the roots of the polynomial $g(x) - x$ (of which there are only finitely many), and to solve this problem one can use a variety of methods, like for example Newton's method.

share|cite|improve this answer
Yep, whenever you are iterating a map you are likely to find crazy behavior. – Eric Haengel Nov 30 '10 at 15:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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