递归 T(n)= 2T(n-1) + (2^n)

Question

有人可以帮我解决这个问题吗？

Use iteration method to solve it. T(n)= 2T(n-1) + (2^n) , T(0) = 1

步骤说明将不胜感激。

我尝试如下解决递归问题

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

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

T(n-2) = 2T(n-3) + 2^(n-2)

T(n-3) = 2T(n-4) + 2^(n-3)

...

T(0) = 1

然后：

T(n) = 2^k * T(n-k) + ... 这就是我卡住的地方。

Answer 1

好吧，让我们计算一些小值 n:

T(0) =   1
T(1) =   4
T(2) =  12
T(3) =  32
T(4) =  80
T(5) = 192

函数似乎是指数函数；我们有 2^n 个术语，这就是为什么让我们检查是否

T(n) = f(n) * 2^n

其中 f(n) 是某个未知函数。如果我们除以 2^n 我们有 f(n) = T(n) / 2^n

T(0) / 2^0 = 1
T(1) / 2^1 = 2
T(2) / 2^2 = 3
T(3) / 2^3 = 4

看起来很清楚 f(n) = n + 1 和

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

现在让我们通过归纳法证明。

基础： 它适用于 n = 0：(0 + 1) * 2^0 = 1

步骤： 从 T(n - 1) = n * 2^(n - 1) 我们有

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

所以，如果 T(n - 1) 成立，T(n) 也成立。

Q.E.D.

的闭式

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

是

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

作弊方式：试试oeis (on-line encyclopedia of integer sequences) and you'll find A001787

The Recurrence T(n)= 2T(n-1) + (2^n)