info prev up next book cdrom email home

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,

\begin{displaymath}
x_n=x_{n-1}x_{n-2}
\end{displaymath} (1)

is a quadratic recurrence. Another simple example is
\begin{displaymath}
x_n=(x_{n-1})^2
\end{displaymath} (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
\begin{displaymath}
y_n=(y_{n-1})^2+1
\end{displaymath} (3)

with $y_0=1$. This has solution
\begin{displaymath}
y_n=\left\lfloor{c^{2^n}}\right\rfloor ,
\end{displaymath} (4)

where
\begin{displaymath}
c=\mathop{\rm exp}\nolimits \left[{\,\sum_{j=0}^\infty 2^{-j-1}\ln(1+{y_j}^{-2})}\right]=1.502836801\ldots
\end{displaymath} (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,
\begin{displaymath}
S_n=\sum_{i=1}^n {1\over z_i},
\end{displaymath} (6)

where $1<z_1<\ldots<z_n$ are integers. The solution is given by the recurrence
\begin{displaymath}
z_n=(z_{n-1})^2-z_{n-1}+1,
\end{displaymath} (7)

with $z_1=2$. This has a closed solution as
\begin{displaymath}
z_n=\left\lfloor{d^{2^n}+{\textstyle{1\over 2}}}\right\rfloor
\end{displaymath} (8)

where


\begin{displaymath}
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
\end{displaymath} (9)

(Aho and Sloane 1973). A final example is the well-known recurrence
\begin{displaymath}
c_n=(c_{n-1})^2-\mu
\end{displaymath} (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



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25