How would one solve the recurrence relation $a_{n+1}=a_n^2$ for, say, $a_0=2$? The solution seems to be $a(n)=2^{2^n}$, but how would one get to that conclusion?
Furthermore, how would one solve a recurrence relation of the form $a_{n+1}=a_n^k$ for some nonnegative integer $k$? The case for $k=0,1$ is rather easy, but after that I'm stumped.
Thanks!
Best Answer
Another approach: take logarithms, and set $b_n=\log a_n$ so that $$b_{n+1}=2b_n$$ This gives a standard linear recurrence with solution $$(\log a_n=)\text{ }b_n=2^nb_0=2^n\log a_0=\log a_0^{2^n}$$
And conclude. I mention it because though it is not necessary here, transformations of this kind can sometimes put an equation into a form you can solve, even in more complex problems. This deals with your $a_n^k$ example with $c_n=\log a_n$ so that $$c_{n+1}=kc_n \text { whence }c_n=k^nc_0$$ and follow the same argument.