|
|
一篇很厉害的博文: Slyish method for bounding
有一个数列（算法用掉的资源数目）是归纳定义的：
\begin{aligned}&a_0=a_1=0,\\&a_{2n}=4a_n+4,\\&a_{2n+1}=2a_n+2a_{n+1}+4.\end{aligned}根据递推式和首项，$a_{n+1}$ 的普通幂级数生成函数 $f\left(x\right)$ 满足方程$$f{(x)}=2{(x+1)}^2f{(x^2)}+\frac{4x}{1-x}.$$两侧同乘 ${\left({1-x}\right)}^2\log x$ 再叠加（我懒得验证形式表达式这样做对不对，待会儿说这事儿），得到$$f{(x)}=\frac1{{(1-x)}^2}\sum_{n=0}^\infty2^{n+2}x^{2^n}{(1-x^{2^n})}$$所以\begin{aligned}a_{n+1}=&\sum_{k=0}^t{(n+1-2^k)}2^{k+2}-\sum_{k=0}^{t-1}{(n+1-2^{k+1})}2^{k+2}\\=&4{(n+1)}2^t-\frac13{(8⋅4^t+4)},\end{aligned}其中 $t=\left\lfloor{\log_2 n}\right\rfloor$。经过验算这个表达式是正确的（通过前 1000 项验算，并检查该级数符合之前的方程），因此之前我没有验证形式表达式运算合理性的事情，就请大家忘记吧，这个结果是我观（瞪）察（眼）得到的（所谓“注意到”）。
如何证明这个表达式对于任意$n$都是正确的呢 |
|
