Special General Term Formulas
For readers interested in mathematics or programming, the Fibonacci sequence is likely very familiar:
0, 1, 1, 2, 3, 5, 8, 13, ...
It is generated by the recurrence relation: a_{n+2}=a_{n+1}+a_n,\quad a_0=0,a_1=1 Readers may have already seen its general term 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] Suppose we did not have the insight to derive such a complex expression. However, by studying the sequence, we find that as the terms grow larger, the ratio of adjacent terms tends toward a constant. This constant is (assuming we only discovered the numerical value and not the radical form): \beta=\frac{1 + \sqrt{5}}{2}=1.61803398\dots Therefore, we might think of using a geometric progression \alpha \beta^n to approximate this sequence. Through numerical calculation, we find that \alpha indeed tends toward a constant, which is: \alpha=\frac{1}{\sqrt{5}}=0.4472135\dots Later, we discover that the general term of the Fibonacci sequence can be expressed as: a_n=\left[\alpha \beta^n\right] where [x] denotes rounding x to the nearest integer. This result can, of course, be strictly proven. But we only focus on the novelty here: it shows that the general term of some sequences can be expressed as the rounding of an irrational sequence, which is a rather peculiar type of general term formula. Below, we consider the nonlinear recurrence: a_{n+1}=a_n^2+c where a_0 and c are positive. We will find that this leads to a similar rounding-based general term.
Quadratic Nonlinear Recurrence
It can be seen that if c=0, the general term is easy to find: a_n=a_0^{2^n}. This is a rapidly growing sequence (when a_0 > 1). If c is non-zero, it remains a sequence that grows extremely fast (double exponential, like Fermat numbers). For example, when a_0=1, c=1, we have:
1, 2, 5, 26, 677, 458330, 210066388901, ...
When n is relatively large, the difference between a_n^2+c and a_n^2 is negligible. Thus, we can still assume there exists some constant k such that a_n \sim k^{2^n}. The research approach in this article is based on this idea, and the calculations primarily come from the expert kastin on the Mathematics R&D Forum.
Let x_n = \ln a_n, then: x_{n+1}=2x_n+\ln\left(1+\frac{1}{a_n^2}\right) Iterating gives: \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, it is clear that the first infinite series must converge. Thus, we can find its (approximate) limit value (currently only through numerical methods). Then we estimate the influence of the second series. Thus: \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} Then: a_n > \exp\left(-\ln\left(1+\frac{1}{a_n^2}\right)\right)k^{2^n} which implies: a_n+\frac{1}{a_n} > k^{2^n} Similarly, we have: r_n > -\ln\left(1+\frac{1}{a_n^2}\right) So: a_n < \exp\left(\ln\left(1+\frac{1}{a_n^2}\right)\right)k^{2^n} which implies: k^{2^n}> a_n \left/\left(1+\frac{1}{a_n^2}\right)\right. > a_n - \frac{1}{a_n} Consequently: \left|a_n-k^{2^n}\right| < \frac{1}{a_n} < \frac{1}{2}\quad (n\geq 1) That is to say, a_n is the integer closest to k^{2^n}. Thus we obtain the general term formula: a_n=\left[k^{2^n}\right] In fact, it can be further shown that this rounding symbol always represents the floor function (always rounding down). This is a result obtained by Aho and Sloane in 1973.
Programming Calculation
Below is the Python code to calculate k:
from math import log, exp
n=6 # Calculating 6 steps is already very accurate.
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)The result is:
k=1.5028368010497564...
It should be noted that, in principle, calculating k accurately requires knowing all a_n. Otherwise, the approximate k calculated can only be used for the first few terms, as the error will grow later. Thus, this work seems to put the cart before the horse; if you want to calculate the specific value of a_n, the best method is still honest recursion. However, for a sequence, what we want to do is not just calculate each term, but also analyze its behavior. Writing the solution in this form helps us see how it grows—essentially double exponential growth with k as the base!
Method Review
It can be seen that our main idea for finding the general term of a quadratic nonlinear recurrence is to recognize that the sequence is increasing. We can then assume that when n is large, the influence of the constant is very small, making it similar to the case without a constant, thereby allowing us to estimate the general term formula. Similarly, this method can be extended to cubic or even higher-order cases. The logic and calculations are similar, primarily because when n is very large, the general term depends almost entirely on the highest-order term. In fact, the constant k in the example above can be more concisely expressed as: k=\lim_{n\to\infty}\left(a_n\right)^{2^{-n}}
At the same time, comparing this with the Fibonacci sequence, we can write the general term of the Fibonacci sequence in a rounded form. Compared to the non-rounded general term formula, it has an additional term (a negative power) that “fills in” the part handled by rounding. Does this mean that for quadratic nonlinear recurrences, there might also exist another term to supplement the rounded part, thereby removing the rounding symbol? Surprisingly, for certain quadratic nonlinear recurrences, this is indeed the case! However, we will discuss this in the future.
However, there are other nonlinear recurrence problems, 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 positive constants, and generally \alpha \gg \beta. In such cases, the behavior of the solution is very well-behaved (the S-shaped curve), but we have not yet been able to write its explicit solution well—not even an approximation higher than the first order. Therefore, if you are interested, you can continue research in this direction.