Quadratic Recurrence

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

A quadratic recurrence is a Recurrence Relation on a Sequence of numbers $\{x_n\}$ expressing $x_n$ as a second degree polynomial in $x_k$ with $k<n$. For example,

$$x_n=x_{n-1}x_{n-2}$$ (1)

is a quadratic recurrence. Another simple example is

$$x_n=(x_{n-1})^2$$ (2)

with $x_0=2$, which has solution $x_n=2^{2^n}$. Another example is the number of ``strongly'' binary trees of height $\leq n$, given by

$$y_n=(y_{n-1})^2+1$$ (3)

with $y_0=1$. This has solution

$$y_n=\left\lfloor{c^{2^n}}\right\rfloor ,$$ (4)

where

$$c=\mathop{\rm exp}\nolimits \left[{\,\sum_{j=0}^\infty 2^{-j-1}\ln(1+{y_j}^{-2})}\right]=1.502836801\ldots$$ (5)

and $\left\lfloor{x}\right\rfloor$ is the Floor Function (Aho and Sloane 1973). A third example is the closest strict underapproximation of the number 1,

$$S_n=\sum_{i=1}^n {1\over z_i},$$ (6)

where $1<z_1<\ldots<z_n$ are integers. The solution is given by the recurrence

$$z_n=(z_{n-1})^2-z_{n-1}+1,$$ (7)

with $z_1=2$. This has a closed solution as

$$z_n=\left\lfloor{d^{2^n}+{\textstyle{1\over 2}}}\right\rfloor$$ (8)

where

$$d={\textstyle{1\over 2}}\sqrt{6}\,\mathop{\rm exp}\nolimits ... ...infty 2^{-j-1}\ln[1+(2z_j-1)^{-2}]}\right\}=1.2640847353\ldots$$ (9)

(Aho and Sloane 1973). A final example is the well-known recurrence

$$c_n=(c_{n-1})^2-\mu$$ (10)

with $c_0=0$ used to generate the Mandelbrot Set.

See also Mandelbrot Set, Recurrence Relation

References

Aho, A. V. and Sloane, N. J. A. ``Some Doubly Exponential Sequences.'' Fib. Quart. 11, 429-437, 1973.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/quad/quad.html