Can someone please help me with this recurrences?

T(n)=3T(n - 1) 3

Explanation of steps would be greatly appreciated.

CodePudding user response：

By educated guess, we can try a constant value, let t.

t = 3t   3

is solved by t = -3/2.

Now consider U(n) = T(n) 3/2. The recurrence turns to

U(n) - 3/2 = 3U(n-1) - 9/2   3

or

U(n) = 3U(n-1).

Obviously,

U(n) = U(0) 3^n.