2

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

J. M. ain't a mathematician
  • 75,051
oscar
  • 51
  • 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 00:52
  • yes is t(n)= (t(n-1))^2 +1 the formula is k^2^n – oscar Jul 17 '12 at 00:54
  • 1
    @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 01:13
  • Are you familiar with proof by induction in general? Do you know how to start such a proof? – Emily Jul 17 '12 at 02:56
  • 1
    @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 03:03
  • Please refer to http://mathworld.wolfram.com/QuadraticMap.html#eqn3 – doraemonpaul Jul 17 '12 at 06:57
  • The domain of $n$ is in complex numbers or just in integers? – doraemonpaul Jul 18 '12 at 21:50
  • Got something from an answer below? – Did Jul 25 '12 at 16:32

5 Answers5

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

Did
  • 279,727
1

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

Gerry Myerson
  • 179,216
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?

hollow7
  • 2,455
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?

lab bhattacharjee
  • 274,582
  • 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 03:33
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.

doraemonpaul
  • 16,178
  • 3
  • 31
  • 75