用迭代代入法证明递推关系T(n)=O(n^log m)（m>4）

嘿，你已经找对方向了！迭代法完全能搞定这个递推，你已经迭代3次得到了这个式子：
$$T(n) = m^4T(n/24)+a\left(m\left(\frac{n}{2^3}\right)2 + m\left(\frac{n}{2^2}\right)2+m\left(\frac{n}{2}\right)^2 + n^2\right)$$

咱们直接把这个规律推广到k次迭代，就能得到通用形式：
$$T(n) = m^{kT\left(\frac{n}{2}k}\right) + a n^2 \sum_{i=0}^{k-1} \left( \frac{m}{4} \right)^i$$

接下来用终止条件 ( \frac{n}{2^k} = 1 )，也就是 ( k = \log_2 n ) 代入：

1. 先看第一项：( m^k = m^{\log_2 n} = n^{\log_2 m} )（这里用了对数换底的性质：( a^{\log_b c} = c^{\log_b a} )），而 ( T(1) ) 是常数，所以第一项的量级是 ( O(n^{\log_2 m}) )。
2. 重点分析后面的等比级数：因为 ( m>4 )，所以公比 ( r = \frac{m}{4} > 1 )，这是个递增等比级数，求和公式是：
   $$\sum_{i=0}^{k-1} r^i = \frac{r^k - 1}{r - 1}$$

把 ( r = m/4 ) 和 ( k = \log_2 n ) 代入求和公式：
$$\frac{\left(\frac{m}{4}\right)^{\log_2 n} - 1}{\frac{m}{4} - 1} = \frac{\frac{m^{\log_2 n}}{4^{\log_2 n}} - 1}{\frac{m-4}{4}}$$

这里再做两个关键转换：

• ( 4^{\log_2 n} = (2²⁾{\log_2 n} = n^2 )
• ( m^{\log_2 n} = n^{\log_2 m} )

代入后分子变成 ( \frac{n^{\log_2 m}}{n^2} - 1 = n^{\log_2 m - 2} - 1 )，整个级数乘以 ( a n^2 ) 后得到：
$$a n^2 \times \frac{n^{\log_2 m - 2} - 1}{\frac{m-4}{4}} = \frac{4a}{m-4} \times (n^{\log_2 m} - n^2)$$

现在看量级：因为 ( m>4 )，所以 ( \log_2 m > \log_2 4 = 2 )，也就是说 ( n^{\log_2 m} ) 的增长速度远快于 ( n^2 )，所以 ( n^{\log_2 m} - n^2 = O(n^{\log_2 m}) )。

最后把两项加起来：
$$T(n) = O(n^{\log_2 m}) + O(n^{\log_2 m}) = O(n^{\log_2 m})$$

这样就完成证明啦！核心就是把迭代步骤 generalize 到k次，利用等比级数求和，再结合对数转换和量级比较，就能得出结论。

内容的提问来源于stack exchange，提问作者bananas