如何通过迭代求解递归关系

Question

所以我的教授希望我们那样做。

这些是他的例子：

Tfac(n) = Tfac(n-1) + 1
Tfac(n-1) = Tfac(n-2) + 1
...
Tfac(2) = Tfac(1) + 1
Tfac(1) = const;

Tfac(n)=1+1+…+1+const=n-1+const=O(n)
------------------------------------
Tbin(n) = 2^1.Tbin(n-1) + 2^0
2^1.Tbin(n-1) =2^2.Tbin(n-2) + 2^1
2^2.Tbin(n-2) =2^3.Tbin(n-3) + 2^2
...
2^n-2.Tbin(2) = 2^n-1.Tbin(1) + 2^n-2
2^n-1.Tbin(1) = 2^n-1.const;

Tbin(n)=2^0+2^1+2^2+…+2^n-2+2^n-1+c’2^n-1 =
= 2^n-1+(const-1).2^n-1 = O(2^n)

我不太了解。这些是我2次尝试的一些示例。将不胜感激，以及如何正确进行。

T(1) = 3
T(n) = T(n-1) + n + 4
T(n-1) = T(n-2) + n + 4
...
T(2) = T(1) + n + 4
T(1) = const

T(n) = n + 4 + n + 4 +...+ n + 4 + const = o(n)
-------------------------------
T(1) = 4
T(n) = T(n-1) + n + 3
T(n-1) = T(n-2) + n + 3
...
T(2) = T(1) + n + 3
T(1) = const

T(n) = n + 3 + n + 3 +...+ n + 3 + const = O(n)

Answer 1

这里是第一个解决的示例：

T(n) = T(n-1) + n + 4
     = (T(n-2)+ n-1 + 4) + n + 4
     = ((T(n-3) + n-2 + 4) + n-1 + 4) + n + 4
     ...
     = T(1) + n^2 + 4n - 1 - 2 - 3 - 4 ... - (n-1)
     = 4 + 4n + (n^2 - 1/2*(n^2-n))
     = 4 + 4n + 1/2*n + 1/2*n^2
     = O(n^2)

在您的解决方案中，您忘记了每次迭代后都要写一些术语。使用方括号确实有帮助，因为我必须避免这种情况。