使用迭代法求解递归式：求T(n)=T(n-1)+4n的一般形式

我来帮你一步步拆解这个递归式的迭代展开过程，搞清楚它的一般形式和最终闭合解～

第一步：逐步展开递归式 #

我们从原递归式开始，不断代入后续的递归项：

• 初始式：T(n) = T(n-1) + 4n
• 代入 $T(n-1) = T(n-2) + 4(n-1)$：T(n) = T(n-2) + 4(n-1) + 4n
• 再代入 $T(n-2) = T(n-3) + 4(n-2)$：T(n) = T(n-3) + 4(n-2) + 4(n-1) + 4n

观察这几步的规律，当我们展开k次后，递归式的一般形式就会变成：

T(n) = T(n-k) + 4 * sum_{i=0}^{k-1} (n - i)

第二步：计算求和项 #

接下来我们简化这个求和式 $\sum_{i=0}^{k-1} (n - i)$，这其实是一个首项为 $n$、末项为 $n - k + 1$、项数为 $k$ 的等差数列求和：
$$
\sum_{i=0}^{k-1} (n - i) = \frac{k \times [n + (n - k + 1)]}{2} = \frac{k(2n - k + 1)}{2}
$$

把这个结果代回展开式，得到更简洁的一般形式：

T(n) = T(n-k) + 2k(2n - k + 1)

第三步：推导闭合解（代入基例） #

要得到最终的闭合形式，我们需要代入递归的基例（比如 $T(0) = C$，$C$ 是常数）。当展开到基例时，$k = n$（此时 $n - k = 0$），代入后：

T(n) = T(0) + 2n(2n - n + 1) = C + 2n(n + 1) = 2n² + 2n + C

如果你的基例是 $T(1) = D$，那只需要取 $k = n-1$，代入后也会得到类似的二次函数形式，只是常数项会根据基例调整。

总结 #

• 迭代展开k次后的一般形式：T(n) = T(n-k) + 2k(2n - k + 1)
• 最终的闭合解：$T(n) = 2n² + 2n + C$（C由基例决定）

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