How to prove that $a_n\le 1.51^{2^n}$ for the sequence $a_0 = 1; a_n=a_{n-1}^2 + 1$? I have tried induction, but it doesn't seem to work:
$a_n = a_{n-1}^2 + 1 \le \left(1.51^{2^{n-1}}\right)^2+1 = 1.51^{2^n}+1$.
Any ideas? Thanks!
 A: Let's prove a stronger statement:
$$a_n\le 1.51^{2^n}-1\tag{1}$$
...for $n\ge4$.
Initial step: $a_0=1,a_1=2,a_2=5,a_3=26,a_4=677$. And $1.51^{2^4}-1=729.52$. So the statement is true for $n=4$.
Induction step: Suppose that $a_n\le 1.51^{2^n}-1$. It means that:
$$a_{n+1}=a_n^2+1$$
$$a_{n+1}\le (1.51^{2^n}-1)^2+1$$
$$a_{n+1}\le 1.51^{2^{n+1}}-2\times1.51^{2^n}+2$$
$$a_{n+1}\le 1.51^{2^{n+1}}-2(1.51^{2^n}-1)\tag{2}$$
Notice that:
$$2(1.51^{2^n}-1)\gt2(1.51-1)\gt 1\tag{3}$$
By combining (2) and (3) you get:
$$a_{n+1}\le 1.51^{2^{n+1}}-1$$
...which completes the induction step. So the statement (1) is defintely true and a weaker statement:
$$a_n\le 1.51^{2^n}$$
...is also true for $n\ge 4$.Manual check shows that it's also true for $n=0,1,2,3$ which completes the proof.
A: For
$a_n 
= a_{n-1}^2 + 1
$,
suppose
$a_n
\le uv^{2^n}-1
$.
We will try to determine
$u$ and $v$
so that
$a_{n+1}
\le uv^{2^{n+1}}-1
$.
$\begin{array}\\
a_{n+1}
&= a_{n-1}^2 + 1\\
&\le (uv^{2^{n}}-1)^2 + 1\\
&= u^2v^{2^{n+1}}-2uv^{2^{n}}+1 + 1\\
&= u^2v^{2^{n+1}}-2uv^{2^{n}}+2\\
\end{array}
$
so we want
$u^2v^{2^{n+1}}-2uv^{2^{n}}+2
\le uv^{2^{n+1}}-1
$
or
$u(u-1)v^{2^{n+1}}
\le 2uv^{2^{n}}-3
$.
If
$u=1$ this is
$2v^{2^{n}}
\ge 3
$
or
$v^{2^{n}}
\ge \dfrac32
$
and this will certainly be true for
$v \ge \dfrac32$.
Therefore the induction step
will work
for any $v \ge \dfrac32$
if the induction hypothesis
is true.
As shown in Oldboy's answer,
this is true for
$v = 1.51$,
so that
this $v$ works.
