1

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!

Bonnaduck
  • 4,058

3 Answers3

8

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.

Mark Bennet
  • 100,194
4

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.

Guy
  • 8,857
  • 1
  • 28
  • 57
  • Sorry, I should have been more clear. How would you get to $2^{2^n}$ in the first place? – Bonnaduck Mar 12 '14 at 19:03
  • 1
    @Bonnaduck your question would then be how would I get to $a_0^{k^n}$ in the first place, yes? Your exact question is just a special case of this right? – Guy Mar 12 '14 at 19:04
  • I did that mostly through intuition, confirming it by induction. It is hard for me to separate it out into separate thought. But I will try my best – Guy Mar 12 '14 at 19:09
  • Assuming that the solution always has the form $a_0^{k^n}$, then yes. For example, when solving recurrences, you may be able to use generating functions as opposed to "guessing" the answer then using induction. For higher powers, (my attempt of) using generating functions doesn't work. So, is there another way to go about it? – Bonnaduck Mar 12 '14 at 19:10
  • @Bonnaduck no. I tried, there don't seem to be methods. The solution is always of this form for your current equation though. Expanding it into a polynomial of more than one term would worsen things though. – Guy Mar 12 '14 at 19:12
1

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.

drhab
  • 151,093