被兔子创飞了

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

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

而且其实理论上,这篇博客的名字应该叫《被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\}\)的递推式:

\[ \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)} \]

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

然后我开始估计了一下这个\(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\)的系数,我们有:

\[ 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} \]

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

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

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

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

首先换元,上面等价于下面这个数列放缩: \[ a_1=\frac1 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} \]

两边求和有: \[ 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} \]

仔细观察下面这个式子: \[ \frac{1}{a_{n+1}}-\frac{1}{a_n}=\frac{1}{1-a_n} \] 我们上面的操作实质上是使用这个式子将\(0<a_n\leq \frac 1 3\)这个放缩给缩紧了,所以我们再用一次这个式子再紧一遍.

\[ \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}\\ \]

两边求和自然有:

\[ \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} \]

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