How to prove that $a_n\le 1.51^{2^n}$ for the sequence $a_0 = 1; a_n=a_{n-1}^2 + 1$?

Question

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!

Answer 1

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.

Answer 2

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.