求解递归方程:T(n) = 3T(n−1) + 1,n>1,T(1) = 1
问题描述:
求解递归方程:T(n) = 3T(n−1) + 1,n>1,T(1) = 1
答
T(1) = 1;
T(2) = 3+1;
T(3) = 3^2+3+1;
.
T(n) = 3^(n-1)+3^(n-2)+...+3+1=(3^n-1)/2;
最后的结果是利用了等比数列求和公式.
好久没做过代数题了,也不知道这样做对不对,你参考一下吧.