# Solving the recurrence $t(n)=(t(n-1))^2 + 1$

I am trying to solve the following recurrence relation: \begin{align*} t(1) & = 1, \\ t(n) & =(t(n-1))^2 + 1. \end{align*} I need to prove that $t(n)= k^{2^{n}}$ for some constant $k$. What is the value of $k$?

How would I go about doing it? thanks

-
If you mean that $t(n)=(t(n-1))^2+1$, then the formula $k^{2n}$ is not correct, as a calculation of the first few terms will show. So there may be a typo. And if you mean asymptotically equal, that doesn't work either, the function as given grows far faster than $k^{2n}$. – André Nicolas Jul 17 '12 at 0:52
yes is t(n)= (t(n-1))^2 +1 the formula is k^2^n – oscar Jul 17 '12 at 0:54
@oscar Even after editing, what you are trying to prove is false. Let $n=1$. Then we have $k^2=1$, so $k=\pm 1$. But this would imply $t(n)=1$ for all $n$, which is trivially false. – Alex Becker Jul 17 '12 at 1:13
Are you familiar with proof by induction in general? Do you know how to start such a proof? – Arkamis Jul 17 '12 at 2:56
@EdGorcenski i dont now how formula use, T(n)=T(n-1)^2 + 1 or T(n)=k^2^n in the induction – oscar Jul 17 '12 at 3:03

Since $t(n)\geqslant1$, $t(n+1)+1=t(n)^2+2\leqslant(t(n)+1)^2$ for every $n\geqslant1$. Iterating and using the initial condition $t(1)+1=2$, one gets $t(n)+1\leqslant2^{2^{n-1}}$, hence $t(n)\lt2^{2^{n-1}}$ for every $n\geqslant1$.

On the other hand, $t(n+1)\gt t(n)^2$ for every $n\geqslant1$. Iterating and using the initial condition $t(2)=2$, one gets $t(n)\gt2^{2^{n-2}}$ for every $n\geqslant2$.

For every $n\geqslant2$, $a^{2^n}\lt t(n)\lt b^{2^n}$ with $a=\sqrt[4]{2}$ and $b=\sqrt{2}$.

Conjecture: $\log_2\log_2 t(n)=n-\kappa+o(1)$ for some $1\leqslant\kappa\lt2$.

Edit: The OEIS page suggested by @Gerry Myerson asserts that $\kappa$ exists and provides a numerical value equivalent to $\kappa=1.7668768^-$.

-

The sequence is tabulated here, and there are some links that you might find helpful.

-

Since T(n) = k^(2^n), T(1) = 1 = k^(2^1) = k^2

Hence, k = 1 or k = -1, which doesn't make sense at all.

You sure you got the question right?

-

If $T(n)=T(n-1)^2+1$ => $T(n)=(T(n-1))^2+1$

If $T(n)=k^{2^n}$ for some k,

$(T(n-1))^2+1 = ({k^{{2^{n-1}}})^2}+1 = k^{2^n}+1$ which can not be equal to $k^{2^n}=T(n)$

What's wrong in these steps?

-
I think we all know $t(n)$ can't equal $k^{2^n}$. We've moved on to noting that it is asymptotic to $k^{2^n}$, for an appropriate choice of $k$. – Gerry Myerson Jul 17 '12 at 13:15
As noted in one of the answers before (and of course in your own answer), it is in fact better than 'just' asymptotic; the relation is so tight that one can find a $k$ such that $t(n) = \left\lfloor k^{2^n}\right\rfloor$ for all $n$. – Steven Stadnicki Sep 11 '12 at 3:33

In fact this recurrence belongs to a linear shifting version of http://mathworld.wolfram.com/QuadraticMap.html#eqn3.

So according to http://mathworld.wolfram.com/QuadraticMap.html#eqn3, this recurrence has the analytical solution when $n$ is any natural number:

$t(n)=\biggl[e^{2^{n-1}\sum\limits_{k=1}^\infty2^{-k}\ln\Bigl(1+\frac{1}{y_k^2}\Bigr)}\biggr]$

For $n$ is any complex number, I still have no idea about its analytical solution.

-