How should I proceed to solve this recurrence relation: $T(n) = T(n - 1)^2$

Question

I tried to solve this recurrence relation, but I was confused when I had to determine the pattern.

$$ T(n) = \begin{cases} 3, & \text{if }n = 0 \\ T(n - 1)^2, & \text{if }n > 0 \end{cases} $$

Answer 1

Take a guess at it. $T(0) = 3$

$T(1) = T(0)^2 = 3^2$

$T(2) = T(1)^2 = (3^2)^2 = 3^4 $

$T(3) = T(2)^2 = (3^4)^2 = 3^8 $

$T(4) = T(3)^2 = (3^8)^2 = 3^{16}$

This would suggest guessing $T(n) = 3^{2^n}$, which you can plug into the recurrence and see if its right.