鸡贼地 bound 一个数列

我发现当我的生活充实的时候就有有趣的 blog 可以写！因为一忙起来，就要忙里偷闲，然后就会胡思乱想，然后就可能有有意思的东西。

• 北京时间早八点三刻更新：再次证明我可能是个智障。
• 北京时间十点半更新：同学的差分大法。
• 8 月 10 日 更新。

我在实现一个算法，于是忙里偷闲，于是胡思乱想。有一个数列（算法用掉的资源数目）是归纳定义的：$\SeqDef$当然计算机科学家喜欢的写法是 $a_n=4a_{n/2}+\Theta\left(1\right)$，用主定理一下就知道 $a_n=\Theta\left(n^2\right)$。虽然在实际实现的过程中用不到这个数列的具体数值，但是我还是对这个数列很感兴趣，比如，我可能希望在算法开始之前预估（upper-bound 之）这个数字。

写程序算这个数列的前 1000 项，并计算 $n^{-2}a_n$，可以发现这个比值在 1.3 到 1.5 之间徘徊，而且从未到达 1.5。容易猜想 $n^{-2}a_n\leq 1.5$，实际上我认为 1.5 应该是这个比值的上极限。

那么怎么验证这件事情呢？（理论计算机科学家的毛病？总想证明！）一个简单的思路是去证明 $a_n\leq 1.5n^2$。有一个方法叫做归纳法，有一个方法叫做加强命题，有一个方法叫做待定系数。直接归纳做不了，自然地想到加强命题，加强到什么样子呢？那就待定系数决定好了。就是这么鸡贼！实际上这个方法我用过不少次，但是从来没有把这种组合明确说出来；明确说出来之后觉得好猥琐……

考虑归纳证明 $a_n\leq An^2+Bn+C$，随便胡写一点，可以发现选择的数要满足不等式组$\FirstAttempt$其中 $n$ 跑遍正整数，这等价于$\FirstAttemptEquiv$在这个条件下最小化 $A$，这是一个线性规划问题，算出来 $A=2,B=-2,C=0$ 是最优解。

结论强度不够啊！

嗯，这时候需要一点点小技巧——所谓“前有限项没必要关心”。简单来说想要得到渐近的 bound，我们可以从下标较大的地方开始。如果从第 $2n$ 项（或第 $2n+1$ 项）开始归纳，我们只需要不等式对 $n,\cdots,2n-1$（或外加 $2n$ 这项）这些项成立。归纳推理用到的不等式也有所放松。

经过简单的尝试，如果从 $a_4$ 开始用归纳，需要满足的不等式组是$\SecondAttempt$最优解是 $a=\frac32,b=-\frac12,c=-1$。

Tada! 这就验证了 $n^{-2}a_n\leq 1.5$，不过具体是不是上极限暂时还不知道。

现在我想调查一下：你觉得这种操作常见吗？还是说这是一个骚操作？回复或者通过别的渠道告诉我 😁

聪明反被聪明误

把这篇博文传出去给一些朋友看，胡波有一个很聪明的做法。先上一个图，毕竟“数形结合百般好，隔裂分家万事休”：

这个图暗示了两件事儿：

• 整体形状是二次函数；（和主定理吻合）
• 分段直线？

胡波注意到 $a_{2n+1}=\frac12\left({a_{2n}+a_{2n+2}}\right)$。如果我们按照这样的方法计算：

1. 从只有一项 $a_1=0$ 开始；
2. 把当前所有项乘 4 再加 4，得到更大范围的偶数项；
3. 把更大范围里的奇数项通过相邻两项的平均数算出来；
4. 现在有结果的范围扩大了一倍，回到第 2 步继续；

则容易用归纳法得到：$a_n$ 在 $2^t\leq n\leq 2^{t+1}$ 范围内是 $n$ 的一次函数，对所有自然数 $t$。因此只要计算 $a_{2^n}$ 的通项自然就得到了 $a_n$ 的通项，用常用技巧把递推式变成方便求和的样子$4^{-n-1}a_{2^{n+1}}=4^{-n}a_{2^n}+4^{-n},$反复运用该递推式有$\TermForTwoPow$于是得出结论。

同学的差分大法

我的同学 MT 表示可以考虑数列 $d_n=a_n-a_{n-1}$，这样可以得到 $d_n=2d_{\left\lceil{n/2}\right\rceil}$，于是 $d_n=2^{\left\lceil{\log_2 n}\right\rceil+2}$，后面略。他还发现了我的一个笔误。以下是我们并不有趣的微信对话。

8 月 10 日更新：实际上该方法（作差分）是和普通幂级数生成函数里的解法不谋而合的，因为对普通幂级数生成函数乘 $\left({1-x}\right)$ 就是作差分；在我的解法里，我做了两次差分，这就会得到一个“经常是 0，在 2 的乘方下标附近不是 0”的数列，而求两次前缀和等同于和 $a_n=n$（或者下标有个什么错位之类的）作卷积。