Solving the recurrence relation $a_{n+1}=a_n^2$

Question

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!

Answer 1

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.

Answer 2

Induction, of course!

Base Step: $a_n=2^{2^n}$ is obviously true for $n=0$

Hypothesis: Let this be true for some $n\ge0$

Inductive step: $a_{n+1} = a_n^2 = (2^{2^n})^2 = 2^{{2^n}*2} = 2^{2^{n+1}}$

Thus proved.

As for your second question, note that $a_{n+1}=a_n^k$. I state that $a_{n} = a_0^{k^n}$. Try to prove by induction.

EDIT: Attempt to get a closed form through "not induction"

We have, $a_0 = 2$, $a_1=a_0^k$,$a_2=a_1^k=(a_0^k)^k$

Similarly, $a_3=a_2^k=(a_0^k)^k)^k$

It is easy to see in this pattern that after $n$ iterations, there are $n$ $k$'s multiplied leading to our expression of $a_0^{k^n}$

It gets very messy if the original recurrence is polynomial with more than one term though.

Answer 3

On your question 'how would one get to that conclusion?' I would say: you just calculate $a_n$ for -let's say - $n=0,1,2,3$ and then clearly a pattern shows up wich makes you suspect that $a_n=2^{2^n}$. Next you try to prove this by induction, and you succeed. That's how I would get to that conclusion.

If $a_{0}=2$ and $a_{n+1}=a_{n}^{k}$ then you find $a_{1}=2^{k}$, $a_{2}=\left(2^{k}\right)^{k}=2^{k^{2}}$, $a_{3}=\left(2^{k^{2}}\right)^{k}=2^{k^{3}}$. This is enough to suspect that $a_{n}=2^{k^{n}}$ and with induction that can easily be verified.