Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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 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
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 3:03

5 Answers 5

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

share|improve this answer

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

share|improve this answer

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?

share|improve this answer

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?

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.