如何用迭代法求解递推关系式T(n)=2T(n-1)+2^n，T(0)=1

初始条件：T(0)=1

步骤1：逐层迭代展开递推关系 #

从原始递推式开始逐步代入下层递推：

1. 原式：T(n) = 2T(n-1) + 2^n
2. 代入T(n-1) = 2T(n-2) + 2^(n-1)：

   T(n) = 2 * [2T(n-2) + 2^(n-1)] + 2^n
        = 2² T(n-2) + 2^n + 2^n
   

3. 代入T(n-2) = 2T(n-3) + 2^(n-2)：

   T(n) = 2² * [2T(n-3) + 2^(n-2)] + 2^n + 2^n
        = 2³ T(n-3) + 2^n + 2^n + 2^n
   

规律：每迭代1次，T的系数指数+1，同时额外新增1个2^n项

步骤2：归纳k次展开后的通用形式 #

迭代k次后，式子可总结为：
T(n) = 2^k * T(n - k) + k * 2^n

步骤3：代入初始条件求解闭式 #

根据初始条件T(0)=1，取k=n即可让n-k=0，代入通用式得：

T(n) = 2^n * T(0) + n * 2^n
     = 2^n * 1 + n * 2^n
     = 2^n (n + 1)

正确性验证 #

• n=0：递推值T(0)=1，闭式计算结果2^0*(0+1)=1，二者一致
• n=1：递推值T(1)=2*T(0)+2^1=4，闭式计算结果2^1*(1+1)=4，二者一致
• n=2：递推值T(2)=2*T(1)+2^2=12，闭式计算结果2^2*(2+1)=12，二者一致

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