Can anybody help me to Solve the following recurrence using iteration/expansion method?
1.T(n)= T(n-1)+ n,T(0)= 1
The solution should be like this way
T(k)=T(K-1)+K
T(K-1)=T(K-2)+(K-1)
......................
所以给出的是:
1. T(n)= T(n-1) + n
2. T(0)= 1
所以它变成这样:
T(0) = 1
T(1) = T(0) + 1 = 2
T(2) = T(1) + 2 = 4
T(3) = T(2) + 3 = 7
T(4) = T(3) + 4 = 11
T(5) = T(4) + 5 = 16
如果你仔细看,它是:
T(k) = sum(k) +1 // sum(k)=1+2+3+4+5 ... + k-1+k
看看高斯所有自然数之和,他告诉我们,sum(k)=(k^2+k)/2
所以你的解决方案应该是:
T(k) = 1 + (k^2+k)/2