Question

求解递归方程：T(n) = 3T(n−1) + 1, n>1, T(1) = 1

求解递归方程：T(n) = 3T(n−1) + 1, n>1, T(1) = 1 ============== 要求详细步骤

Answer 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;
最后的结果是利用了等比数列求和公式。
好久没做过代数题了，也不知道这样做对不对，你参考一下吧。