被兔子创飞了

没想到这个系列博客都出到第三节了.

之所以起这么个名字,是因为下面要开搞的数列很像真理元素的这个视频.但其实下面的操作和这个视频并没有什么关系.

而且其实理论上,这篇博客的名字应该叫《被qyc创飞了(1)》

前天,qyc给我发了一个博客,里面提供了一种非常厉害的估计数列的方法.我一看就觉得超级厉害啊,因为这个题我之前也做过然后被爆杀了,而竟然可以拿科技秒掉.

大概讲一下qyc的神仙操作:

$a_1 = 1 , a_{ n + 1 } - a_n = - \frac{ 1 }{ 3 } a_n^2$

考虑构造一个函数$f ( n )$使得$f ( n ) \approx a_n$,那我们就可以将$a_{ n + 1 } - a_n \approx f_n$.

这个第一眼看上去就很有道理,而事实上也确实很有道理,原因是根据拉格朗日中值定理,$\exists x_0 \in [ n , n + 1 ] , f ‘ ( x_0 ) = f ( n + 1 ) - f ( n )$,而对于增长率变化不大的函数,直接认为$f ‘ ( x_0 ) = f ‘ ( n )$是有理可循的!

@Minuses在知乎上找到了这个东西的系统理论.但是我没有看.

然后,原式子就变成了一个微分方程了,带入$f ( 1 ) = 1$解得$f ( n ) = \frac{ 3 }{ n + 2 }$.这个精度已经足够选出来原本的放缩题的答案了.

但是我不满意!具体数学上教过我们可以用数列估计误差项,那现在我们来考虑一下它的误差项吧!

令$a_n = \frac{ 3 }{ n + 2 } - b_n$,带入化简,得到$\{ b_n \}$的递推式:

$$\begin{aligned} \frac{ 3 }{ n + 3 } - b_{ n + 1 } & = ( \frac{ 3 }{ n + 2 } - b_n ) ( 1 - \frac{ 1 }{ n + 2 } + \frac{ b_n }{ 3 } ) \\ b_{ n + 1 } - \frac{ 3 }{ n + 3 } & = ( b_n - \frac{ 3 }{ n + 2 } ) ( \frac{ n + 1 }{ n + 2 } + \frac{ b_n }{ 3 } ) \\ b_1 & = 0 , b_{ n + 1 } = \frac{ b_n^2 }{ 3 } + \frac{ n }{ n + 2 } b_n + \frac{ 3 }{ ( n + 2 )^2 ( n + 3 ) } \end{aligned}$$

算到这里,我们可以很轻易使用数学归纳法算出$b_n \leq \frac{ 1 }{ 4 n }$,这个精度已经挺不错的了,但是也让人觉得很不满意,因为这个误差项怎么和估计项是同阶的啊.

然后我开始估计了一下这个$b_n$的阶,因为我其实没学过什么高超的高数技巧,所以我使用了OI的一些技巧来估计,不妨假设$b_n^2 < < b_n$:

$b_{ n + 1 } = O ( 1 ) b_n + O ( \frac{ 1 }{ n^3 } )$.

那么$b_n$应该是$O ( \frac{ 1 }{ n^2 } )$级别的对吧!然后我就开始算,算了一晚上也没放出来一个式子,相当自闭.

晚上回家咨询了一下汪神wzm,得知了这个$b_n$是$O ( \frac{ \ln n }{ n^2 } )$级别的,这下白算一晚上了.

如何理解这个级别?考虑别乱动$b_n$的系数,我们有:

$$\begin{aligned} b_{ n + 1 } & = \frac{ n }{ n + 2 } b_n + \frac{ 1 }{ n ( n + 1 ) ( n + 2 ) } \\ ( n + 1 ) ( n + 2 ) b_{ n + 1 } & = n ( n + 1 ) b_n + \frac{ 1 }{ n } \\ g ( n ) & = n ( n + 1 ) b_n , g ' ( n ) = \frac{ 1 }{ n } , g ( n ) = \ln n \\ b_n & = \frac{ \ln n }{ n^2 } \end{aligned}$$

这警戒我们以后乱估计的时候千万别把$O ( n^{ \epsilon } )$和$O ( 1 )$搞混了,警钟长鸣.

这个时候大概估计一下会发现$b_n \leq \frac{ 3 \ln n }{ n ( n + 1 ) }$.

但是如果你尝试带入数学归纳,会发现完全做不动.怎么办呢?

在这个问题被搞出来后两个周,我妈的一位同事给出了纯文化课的牛逼做法,下面来介绍一下这个做法并且终结此题:

首先换元,上面等价于下面这个数列放缩:

$$a_1 = \frac{ 1 }{ 3 } , a_{ n + 1 } = - a_n ( a_n - 1 )$$

观察形式,注意到$a_n ( a_n - 1 )$这个东西很像一个类似裂项的东西,因此两边取倒数,自然有:

$$\frac{ 1 }{ a_{ n + 1 } } - \frac{ 1 }{ a_n } = \frac{ 1 }{ 1 - a_n }$$

考虑$0 < a_n \leq \frac{ 1 }{ 3 }$,于是我们有下面这个不等式:

$$1 < \frac{ 1 }{ a_{ n + 1 } } - \frac{ 1 }{ a_n } \leq \frac{ 3 }{ 2 }$$

两边求和有:

$$\begin{aligned} n & \leq \frac{ 1 }{ a_{ n + 1 } } - 3 \leq \frac{ 3 }{ 2 } n \\ \frac{ 2 }{ 3 ( n + 1 ) } & \leq a_n \leq \frac{ 1 }{ n + 2 } \end{aligned}$$

仔细观察下面这个式子:

$$\frac{ 1 }{ a_{ n + 1 } } - \frac{ 1 }{ a_n } = \frac{ 1 }{ 1 - a_n }$$

我们上面的操作实质上是使用这个式子将$0 < a_n \leq \frac{ 1 }{ 3 }$这个放缩给缩紧了,所以我们再用一次这个式子再紧一遍.

$$\begin{aligned} \frac{ 1 }{ a_{ n + 1 } } - \frac{ 1 }{ a_n } & \leq \frac{ 1 }{ 1 - \frac{ 1 }{ n + 2 } } = \frac{ n + 2 }{ n + 1 } = 1 + \frac{ 1 }{ n + 1 } \\ \end{aligned}$$

两边求和自然有:

$$\begin{aligned} \frac{ 1 }{ a_{ n + 1 } } - 3 & \leq n + \sum_{ k = 2 }^{ n + 1 } \frac{ 1 }{ k } \leq n + \ln ( n + 1 ) \\ a_n & \geq \frac{ 1 }{ n + 2 + \ln n } \end{aligned}$$

这个界甚至比我们给出的界还要紧.而且似乎继续迭代可以得到更紧的解!相当牛逼!