Resolver la recurrencia $t(n)=(t(n-1))^2 + 1$

Question

Estoy intentando resolver la siguiente relación de recurrencia: \begin{align*} t(1) & = 1, \\ t(n) & =(t(n-1))^2 + 1. \end{align*} Necesito probar que $t(n)= k^{2^{n}}$ para alguna constante $k$ . ¿Cuál es el valor de $k$ ?

¿Cómo puedo hacerlo? Gracias

Answer 1

Desde $t(n)\geqslant1$ , $t(n+1)+1=t(n)^2+2\leqslant(t(n)+1)^2$ para cada $n\geqslant1$ . Iterar y utilizar la condición inicial $t(1)+1=2$ se obtiene $t(n)+1\leqslant2^{2^{n-1}}$ Por lo tanto $t(n)\lt2^{2^{n-1}}$ para cada $n\geqslant1$ .

Por otro lado, $t(n+1)\gt t(n)^2$ para cada $n\geqslant1$ . Iterar y utilizar la condición inicial $t(2)=2$ se obtiene $t(n)\gt2^{2^{n-2}}$ para cada $n\geqslant2$ .

Por cada $n\geqslant2$ , $a^{2^n}\lt t(n)\lt b^{2^n}$ con $a=\sqrt[4]{2}$ y $b=\sqrt{2}$ .

Conjetura: $\log_2\log_2 t(n)=n-\kappa+o(1)$ para algunos $1\leqslant\kappa\lt2$ .

Edita: En Página de la OEIS sugerido por @Gerry Myerson afirma que $\kappa$ existe y proporciona un valor numérico equivalente a $\kappa=1.7668768^-$ .

Answer 2

La secuencia está tabulada aquí y hay algunos enlaces que pueden resultarle útiles.

Answer 3

Como T(n) = k^(2^n), T(1) = 1 = k^(2^1) = k^2

Por lo tanto, k = 1 o k = -1, lo que no tiene ningún sentido.

¿Seguro que has entendido bien la pregunta?

Answer 4

Si $T(n)=T(n-1)^2+1$ => $T(n)=(T(n-1))^2+1$

Si $T(n)=k^{2^n}$ para algún k,

$(T(n-1))^2+1 = ({k^{{2^{n-1}}})^2}+1 = k^{2^n}+1 $ que no puede ser igual a $k^{2^n}=T(n)$

¿Qué falla en estos pasos?

Answer 5

De hecho, esta recurrencia pertenece a una versión de desplazamiento lineal de http://mathworld.wolfram.com/QuadraticMap.html#eqn3 .

Según http://mathworld.wolfram.com/QuadraticMap.html#eqn3 esta recurrencia tiene la solución analítica cuando $n$ es cualquier número natural:

$t(n)=\biggl[e^{2^{n-1}\sum\limits_{k=1}^\infty2^{-k}\ln\Bigl(1+\frac{1}{y_k^2}\Bigr)}\biggr]$

Para $n$ es un número complejo cualquiera, sigo sin tener ni idea de su solución analítica.