使用代入法求解递推式T(n)=T(n-1)+n^2的证明正确性验证

证明前提 #

• 仅使用代入法（基于数学归纳的渐近界证明方法）完成推导验证，不涉及迭代法、主定理等其他求解方案
• 证明目标：存在正常数c和正整数n₀，对所有n ≥ n₀，满足T(n) ≤ c n³
• 递推基例默认取常数边界，通常为T(1) = 1（若你的基例取值不同，仅需对应调整n₀即可，不影响渐近结论）

标准代入法推导步骤 #

1. 归纳假设：假设对所有满足k < n的正整数k，上界成立，即T(k) ≤ c k³。
2. 代入展开：将递推式中的T(n-1)用归纳假设替换：

   T(n) = T(n-1) + n² ≤ c(n-1)³ + n²
   

3. 代数整理：展开右侧三次项，向目标式c n³靠拢：

   c(n-1)³ + n² = c(n³ - 3n² + 3n - 1) + n²
                = c n³ - 3c n² + 3c n - c + n²
   

4. 余项约束：要让T(n) ≤ c n³成立，只需要让展开式中除c n³外的余项部分小于等于0：

   -3c n² + 3c n - c + n² ≤ 0
   

   整理为：

   n²(1 - 3c) + 3c n - c ≤ 0
   

5. 选定常数验证：只要找到满足不等式的正常数c即可，不需要取最小的紧常数。例如取c=1，代入后余项为：

   n²(1-3*1) + 3*1*n -1 = -2n² + 3n -1 = -(2n-1)(n-1)
   

   当n ≥ 1时，(2n-1)(n-1) ≥ 0恒成立，即余项≤0，此时递推式满足T(n) ≤ n³。
6. 基例校验：对应基例T(1)=1，代入得1 ≤ 1*1³ = 1，等号成立，满足约束，因此取c=1, n₀=1即可完成证明。

常见推导错误判定 #

如果你的推导出现以下问题，则证明不成立：

• 代入时直接将(n-1)³放缩为n³，得到T(n) ≤ c n³ + n²，此时存在正的余项n²无法消去，无法推导出最终上界
• 选定常数后未验证余项在n ≥ n₀时恒非正，比如取c=1/3时代入余项为n - 1/3，在n≥1时恒为正，无法满足不等式，需要调整c的取值
• 未验证基例是否满足上界要求，直接推导n较大的情况，会导致归纳链条断裂

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