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,

\end{displaymath} (1)

is a quadratic recurrence. Another simple example is
\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
\end{displaymath} (3)

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

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

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


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

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

See also Mandelbrot Set, Recurrence Relation


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

Finch, S. ``Favorite Mathematical Constants.''

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein