求解递归函数Dots的打印点数：推导输入n对应的输出点数量

首先定义f(n)为调用Dots(n)时打印的总点数，分阶段推导如下：

1. 基础情况 #

当n=1时，函数直接打印1个点，因此：
f(1) = 1

2. 递推关系（n≥2） #

当n>1时，函数执行两部分操作：

• 第一部分：循环调用Dots(1)到Dots(n-1)，这部分总点数为前n-1项的和：f(1) + f(2) + ... + f(n-1)
• 第二部分：两层嵌套循环（i从1到n，j从1到n），共打印n×n = n²个点

由此得到递推式：
f(n) = (f(1)+f(2)+...+f(n-1)) + n²

3. 化简递推式 #

令S(n-1) = f(1)+f(2)+...+f(n-1)，则f(n) = S(n-1) + n²
同理，对于f(n-1)有：f(n-1) = S(n-2) + (n-1)²

将两式相减：
f(n) - f(n-1) = f(n-1) + n² - (n-1)²

展开并化简平方差项：n² - (n-1)² = 2n -1，最终得到简化的递推式：
f(n) = 2f(n-1) + 2n -1（n≥2）

4. 求解递推式 #

这是线性非齐次递推关系，分两步求解：

齐次解 #

特征方程为r - 2 = 0，解得r=2，因此齐次解为：A×2ⁿ（A为常数）

特解 #

由于非齐次项是一次多项式2n-1，假设特解为Bn + C，代入递推式：
Bn + C = 2(B(n-1)+C) + 2n -1

展开右边并整理后对比系数：

• n的系数：B = 2B + 2 → B = -2
• 常数项：代入B=-2，解得C = -3

因此特解为：-2n -3

通解与最终公式 #

通解为齐次解加特解：f(n) = A×2ⁿ -2n -3
代入初始条件f(1)=1，解得A=3，最终得到通项公式：
f(n) = 3×2ⁿ -2n -3

验证 #

• n=1：3×2 -2-3=1，与实际打印数一致
• n=2：3×4 -4-3=5，手动计算：Dots(1)打印1个点+4个点，共5个，正确
• n=3：3×8 -6-3=15，手动计算：Dots(1)+Dots(2)=6个点+9个点，共15个，正确

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