Sucesión recurrente

El problema de esta semana es el siguiente:

Definimos la siguiente sucesión recurrente:

$x_0=1$
$x_{n+1}=3x_n+\lfloor \sqrt{5} x_n \rfloor, \, \forall n\ge 0$ (siendo $\lfloor a \rfloor$ la parte entera de $a$ , es decir, el mayor número entero menor o igual que $a$ )

En particular, se tiene que $x_1=5, \, x_2=26, \, x_3=136$ y $x_4=712$ .

Calcular el valor de $x_{2009}$ .

Como siempre, aunque los cálculos informáticos pueden ser interesantes, se pide un procedimiento matemático para la resolución del problema.

Sin comentarios

Trackback | 26 May, 2009

Bitacoras.com
Tito Eliatron | 26 de May de 2009 | 09:52

Cuantos signos “+” ¿no?
¿acaso será un error del plug-in de latex?
mada | 26 de May de 2009 | 09:57

a mí me pasó también, ver varios signos +, pero solamente desde el popup del coso de google reader de igoogle, acá en el sitio se ve bien.
M | 26 de May de 2009 | 10:42

Veo que $x_{n+1}=x_n\cdot x_1+x_{n-1}+x_{n-2}+\ldots+x_0$ , lo cual permite expresar el valor en términos de potencias de $x_1$ . Con esto parece que debe salir ya. A ver si a la noche con más tiempo…
gaby | 26 de May de 2009 | 12:12

Yo por ahora he llegado a que:
$x_{n+2}=6x_{n+1}-4x_{n}$
M | 26 de May de 2009 | 15:51

Expresando la iteración de Gaby en forma matricial (y diagonalizando) se obtiene
$x_n=\left(\frac{1}{2}+\frac{\sqrt{5}}{5}\right)(3+\sqrt{5})^n+\left(\frac{1}{2}-\frac{\sqrt{5}}{5}\right)(3-\sqrt{5})^n.$
fede | 26 de May de 2009 | 16:19

Según http://www.research.att.com/~njas/sequences/A018903
también cumple la recurrencia
$x_{n+2} = 1 + \left \lfloor \dfrac{ x_{n+1}^2} {x_n} \right\rfloor$ , con $x_0=1$ y $x_1=5$ .

Queda por demostrar que la definición del post, la de gaby y esta última dan la misma secuencia…
Maestrillo | 26 de May de 2009 | 20:25

A partir de lo que dice Gaby es ya fácil. Es una combinación lineal de exponenciales siendo las bases las raíces de la ecuación de segundo grado x^2 – 6x + 4 = 0 y los coeficientes los ajustados mediante el uso de los dos primeros términos de la sucesión.
M | 26 de May de 2009 | 22:38

Para probar la recurrencia de Gaby nos liamos un poco con la parte entera y escribimos a partir de la definición

$x_{n+1}\leq (3+\sqrt{5})x_n<x_{n+1}+1 \,(n\geq 0)$ (1)

y trasladando índices e invirtiendo el $3+\sqrt{5}$ :

$(3-\sqrt{5})x_n\leq 4 x_{n-1}<(3-\sqrt{5})(x_n+1) \,(n\geq 1)$ (2)

De la segunda desigualdad de (1) y la primera de (2) obtenemos sumando que $6x_n-4x_{n-1}<x_{n+1}+1$ .

De la primera de (1) y la segunda de (2) obtenemos al sumar que $x_{n+1}+4x_{n-1}<6x_n+(3-\sqrt{5})$ , lo cual nos da al tratarse de cantidades enteras $x_{n+1}+4x_{n-1}\leq 6x_n$ .

De ambas cosas, $x_{n+1}\leq 6x_n-4x_{n-1}<x_{n+1}+1$ , que nos da la recurrencia de gaby.
gaby | 26 de May de 2009 | 22:54

Serían $x_1=3+\sqrt{5} \\ x_1=3-\sqrt{5}$
Y por lo tanto la combinación lineal sería:
$N=c_1e^{(3+\sqrt{5})x}+c_2e^{(3-\sqrt{5})x}$
$1=c_1+c_2 \\ 5=c_1e^{(3+\sqrt{5})1}+c_2e^{(3-\sqrt{5})1}$
Donde $c_1=\frac{1}{3}$ y $c_2=5e^{\sqrt{5}-3}-\frac{e^{2\sqrt{5}}}{3}$
Con lo que para n=2009 daría por resultado: $9.543256412 \cdot 10^4567$
No se si es el resultado buscado pero se ha hecho lo que se ha podido.
gaby | 26 de May de 2009 | 22:56

El 567 del final esta en el exponente también, sería multiplicado por $10^{4567}$