General term formulas for nonlinear recurrence sequences

Question

It seems to be a well known question: in which cases will there be general term formulas for sequences like $p_n=a p_{n-1} ^2 +b p_{n-1} +c$ where $a, b, c$ are real or complex numbers and n is greater or equal to 1? I think there are something called Julia theorem (maybe I spell it wrong) can explain this, but I never studied dynamic systems, so can anyone tell me something about that?

Answer 1

Polynomial maps $f(z)$ for which there is a general formula for the $n$-th iterate are called integrable. Besides polynomials of degree $1$, there are two types of them: a) those which are conjugate (by an affine map) with $z^d$ and b) those which are conjugate with $T_d$, where $T_d$ is the Chebyshev polynomial, defined by $$\cos dx=T_d(\cos x).$$ For example $f(z)=2z^2-1$, the general formula for the $n$-th iterate is $\cos(2^n\arccos z)$.

The result can be extended to rational functions of one variable. Then we have the third class c) consisting of Lattes functions $L_m$, defined by equations like $$\wp(mx)=L_m(\wp(x)).$$ (These are not all. For a complete list of Lattes functions, see he paper by

A. Douady and J. Hubbard, A proof of Thurston’s topological characterization of rational functions. Zbl 0806.30027 Acta Math. 171, No.2, 263-297 (1993).)

This is not a theorem, because it was never rigorously defined what an "explicit formula" is, but this is a well-extablished "fact". (Instead a map is usually called "integrable" if here is a "non-trivial" family of other maps of the same class which commute with it, see, for example

A. P. Veselov What is an integrable mapping? Zbl 0733.58025 What is integrability, Springer Ser. Nonlinear Dyn., 251-272 (1991).

Remark. In fact "a formula" for the $n$-th iterate exists for every polynomial, namely $f^{*n}=\phi^{-1}\circ(\phi^{d^n})$, where $f^{*n}$ is he $n$-th iterate, and $d$ is the degree of $f$. Here $\phi$ is the so-called Boettcher function of $f$. But Boettcher function is "explicit" exactly in the examples of polynomials listed above as a), b).

Remark 2. The result for polynomials is indeed due to P. Fatou and G. Julia (independently) and the result for rational functions to J. F. Ritt.

Answer 2

See Mathworld, where it is stated, "While some quadratic maps are solvable in closed form, most are not." Examples with a closed-form solution are $p_n=p_{n-1}^2$, $p_n=p_{n-1}^2+1$ with $p_0=1$, $p_n=p_{n-1}^2-p_{n-1}+1$ with $p_1=2$, and of course anything that you can reduce to these forms by completing the square.