Prove an inequality by induction

Question

Let $a_0=1$, $a_1=15$, and $$a_n=a_{n-1}(a_{n-2})^2+1,\quad n\geq 2.$$ Show that $a_n<2^{2^{n+1}}$, for all $n\geq 0$.

Using induction, I get stuck to prove the inductive case. I get that $$a_{n+1}-1<2^{2^{n+2}}.$$ and do not know hos to continue. So the problem is to show that the difference between $a_n$ and $2^{2^{n+1}}$ is $\geq 1$. Is there another way to do it?

Thank you

Answer 1

Because by the assumption of an induction $$a_n\leq\left(2^{2^n}-1\right)\left(2^{2^{n-1}}-1\right)^2+1=2^{2^{n+1}}-2^{2^n+2^{n-1}+1}+2^{2^{n-1}+1}<2^{2^{n+1}}.$$

Answer 2

Let $t=2^{2^{k+1}}$. If $a_k\le2^{2^{k+1}}-1=t-1$ and $a_{k+1}\le2^{2^{k+2}}-1=t^2-1$,$$\begin{align}a_{k+2}&\le(t-1)^2(t^2-1)+1\\&=(t^2-2t+1)(t^2-1)+1\\&=(t^2+1)(t^2-1)-2t(t^2-1)+1\\&\le t^4-1\end{align}$$completes your inductive step, and uses only $t(t^2-1)\ge1$.

Answer 3

The relationship given is of the form $$a_n=f(a_{n-1}, a_{n-2})$$ in other words, your $a_n$ is based off two previous iterates, not just one. This means you need to make two base cases, and two assumptions.

First our base cases, we see $a_2=16<256=2^{2^3}$ and $a_3=3601<65536=2^{2^4}$, so these check out.

Then, we assume that $a_n<2^{2^{n+1}}$ and $a_{n+1}<2^{2^{n+2}}$ and use that to show that $a_{n+2}<2^{2^{n+3}}$