被兔子创飞了
没想到这个系列博客都出到第三节了.
之所以起这么个名字,是因为下面要开搞的数列很像真理元素的这个视频.但其实下面的操作和这个视频并没有什么关系.
而且其实理论上,这篇博客的名字应该叫《被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} \]
这个界甚至比我们给出的界还要紧.而且似乎继续迭代可以得到更紧的解!相当牛逼!