A Peculiar Closed-Form Formula: Quadratic Nonlinear Recurrences

特殊的通项公式：二次非线性递推 苏剑林 · 2014-11-12 · Mathematics analysis construction nonlinear

A Peculiar Closed-Form Formula

Readers interested in mathematics or programming are surely already familiar with the Fibonacci sequence

0, 1, 1, 2, 3, 5, 8, 13, ...

which is generated by the recurrence

$$a_{n+2}=a_{n+1}+a_n,\quad a_0=0,a_1=1$$

You have probably also seen its closed-form formula

$$a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]$$

Let's suppose for a moment that we're not clever enough to derive this complicated expression. But by studying the sequence, we notice that as the terms grow larger, the ratio of consecutive terms tends toward a constant. That constant is (assuming we've only observed the later values, without having derived the radical expression above)

$$\beta=\frac{1 + \sqrt{5}}{2}=1.61803398\dots$$more

So it's natural to try approximating the sequence with a geometric sequence $\alpha \beta^n$, and by numerical computation we find that $\alpha$ indeed tends toward a constant, namely

$$\alpha=\frac{1}{\sqrt{5}}=0.4472135\dots$$

We then discover that the general term of the Fibonacci sequence can be written as

$$a_n=\left[\alpha \beta^n\right]$$

where $\left[x\right]$ denotes rounding $x$ to the nearest integer. This result can of course be proved rigorously, but here we only want to note the novel feature that emerges: some sequences have a general term that can be expressed as the rounding of an irrational sequence. This is a rather peculiar type of closed-form formula. Below we consider the nonlinear recurrence

$$a_{n+1}=a_n^2+c$$

where both $a_0$ and $c$ are positive. We'll find that this leads to a similar rounding-based closed form.

Quadratic Nonlinear Recurrence

Notice that if $c=0$, the general term is easy to find: we have $a_n=a_0^{2^n}$, which is a rapidly growing sequence (when $a_0 > 1$). If $c$ is nonzero, the sequence grows even faster — an exponential of an exponential, much like Fermat numbers. For instance, when $a_0=1,c=1$, we get

1, 2, 5, 26, 677, 458330, 210066388901, ...

When $n$ is large enough, the difference between $a_n^2+c$ and $a_n^2$ becomes negligible. So we may still expect there to be some constant $k$ such that $a_n\sim k^{2^n}$ holds. The approach in this article is based on exactly this idea, and the calculations are largely drawn from kastin on the Mathematics Research Forum.

Let $x_n=\ln a_n$; then

$$x_{n+1}=2x_n+\ln\left(1+\frac{1}{a_n^2}\right)$$

Iterating, we obtain

$$\begin{aligned}x_n=&2^n x_0 +\sum_{i=0}^{n-1} 2^{n-i}\ln\left(1+\frac{1}{a_i^2}\right)\\ =&2^n x_0+\sum_{i=0}^{\infty}2^{n-1-i}\ln\left(1+\frac{1}{a_i^2}\right) -\sum_{i=n}^{\infty}2^{n-1-i}\ln\left(1+\frac{1}{a_i^2}\right)\\ =&2^n\left(x_0+\sum_{i=0}^{\infty}\frac{1}{2^{i+1}}\ln\left(1+\frac{1}{a_i^2}\right)\right) -2^{n-1}\sum_{i=n}^{\infty}\frac{1}{2^{i}}\ln\left(1+\frac{1}{a_i^2}\right)\end{aligned}$$

From the growth rate of $a_n$ we can see that the first infinite series must converge, so we can (for now, only numerically) compute its approximate limiting value. We then estimate the contribution of the second series. This gives

$$\begin{aligned}a_n=&\exp(x_n)\\ =&\exp(-r_n)k^{2^n}\end{aligned}$$

where

$$\begin{aligned}&k=\exp\left[x_0+\sum_{i=0}^{\infty}\frac{1}{2^{i+1}}\ln\left(1+\frac{1}{a_i^2}\right)\right]\\ &r_n=2^{n-1}\sum_{i=n}^{\infty}\frac{1}{2^{i}}\ln\left(1+\frac{1}{a_i^2}\right) < \ln\left(1+\frac{1}{a_n^2}\right)\end{aligned}$$

so that

$$a_n > \exp\left(-\ln\left(1+\frac{1}{a_n^2}\right)\right)k^{2^n}$$

i.e.

$$a_n+\frac{1}{a_n} > k^{2^n}$$

Similarly, we have

$$r_n > -\ln\left(1+\frac{1}{a_n^2}\right)$$

hence

$$a_n < \exp\left(\ln\left(1+\frac{1}{a_n^2}\right)\right)k^{2^n}$$

i.e.

$$k^{2^n}> a_n \left/\left(1+\frac{1}{a_n^2}\right)\right. > a_n - \frac{1}{a_n}$$

from which

$$\left|a_n-k^{2^n}\right| < \frac{1}{a_n} < \frac{1}{2}\quad (n\geq 1)$$

This means that $a_n$ is the integer closest to $k^{2^n}$, giving us the closed-form formula

$$a_n=\left[k^{2^n}\right]$$

In fact, one can further show that this rounding is always rounding down (there's only "rounding down," never "rounding up"). This is a result obtained by Aho and Sloane in 1973.

Numerical Computation

Below we compute $k$ programmatically. Python code:

from math import log,exp
n=6 # 计算6步已经很精确了。
x=1
l=[log(1+1/x**2)/2]
for i in range(n):
    x=x**2+1
    l.append(log(1+1/x**2)/2**(i+2))

k=exp(sum(l))
print(k)

which gives

k=1.5028368010497564...

Note that, in principle, computing $k$ exactly would require knowing all the $a_n$ in advance — otherwise the approximate $k$ we compute can only be used to reproduce the first few terms accurately, with the error growing for later terms. This seems to put the cart before the horse: if you actually want to compute a specific value of $a_n$, the honest, straightforward recursive computation is still the best method. However, for a sequence, our goal isn't merely to compute each term — we also want to analyze its asymptotic behavior and other properties. Writing down a closed form of this kind helps us see how the sequence grows — essentially as an exponential-of-an-exponential with base $k$!

Discussion of the Method

As we can see, the main idea behind finding the closed form of this quadratic nonlinear recurrence is to notice that the sequence is increasing, so that for large enough terms the effect of the constant becomes negligible. The problem then approximately reduces to the constant-free case, from which we can estimate the general formula. This method generalizes similarly to cubic and even higher-order recurrences — the reasoning and calculations are analogous, relying on the fact that for large $n$, the general term is essentially determined by the highest-order term alone. In fact, the constant $k$ appearing in the example above can be expressed more compactly as

$$k=\lim_{n\to\infty}\left(a_n\right)^{2^{-n}}$$

Comparing this with the Fibonacci sequence, we can also write a rounding-based closed form for the Fibonacci sequence. Compared with the non-rounding closed form, it has exactly one extra term (a negative power), which "fills in" the part removed by rounding. Does this suggest that quadratic nonlinear recurrences might also admit an extra term that compensates for the rounding, allowing us to drop the rounding operation altogether? Remarkably, for certain quadratic nonlinear recurrences, this is indeed the case! But that is a topic for another time.

That said, there are other nonlinear recurrence problems worth mentioning, such as the discrete logistic growth model, whose recurrence is

$$a_{n+1}-a_n=\alpha a_n-\beta a_n^2$$

where $\alpha,\beta$ are all positive, and typically $\alpha \gg \beta$. In such cases, the solution behaves very nicely (the familiar S-shaped curve), yet we still lack a good explicit solution for it — even just a first-order approximation beyond the trivial one. So if you're interested, this could be a promising direction to pursue further.

Reference:

http://mathworld.wolfram.com/QuadraticMap.html