2
$\begingroup$

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

  • 0
    Got somethi$n$g from $a$n answer $b$elow?2012-07-25

5 Answers 5

3

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^-$.

1

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

0

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?

0

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?

  • 0
    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$.2012-09-11
0

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.