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
    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}$.2012-07-17
  • 0
    yes is t(n)= (t(n-1))^2 +1 the formula is k^2^n2012-07-17
  • 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.2012-07-17
  • 0
    Are you familiar with proof by induction in general? Do you know how to start such a proof?2012-07-17
  • 1
    @EdGorcenski i dont now how formula use, T(n)=T(n-1)^2 + 1 or T(n)=k^2^n in the induction2012-07-17
  • 0
    Please refer to http://mathworld.wolfram.com/QuadraticMap.html#eqn32012-07-17
  • 0
    The domain of $n$ is in complex numbers or just in integers?2012-07-18
  • 0
    Got something from an answer below?2012-07-25

5 Answers 5