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
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
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?
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.