domingo, 25 de mayo de 2014

Sucesiones de Horadam - Soluciones enteras


Esta entrada participa en el Carnaval de Matemáticas 5.4, "Martin Gadner"

Durante este curso hemos venido estudiando sucesiones definidas mediante una recurrencia de segundo grado homogénea (sucesiones Horadam). Puede ser curioso estudiar estas sucesiones cuando las soluciones de la ecuación característica sean enteras.

Puedes repasar algo de este tipo de sucesiones en estas entradas que ya hemos publicado:

 http://hojaynumeros.blogspot.com.es/2014/01/recurrencias-lineales-de-segundo-orden.html

En ella se explican las recurrencias de segundo orden y cómo encontrar sus ecuación característica.

En estas otras explicamos ejemplos concretos, que te pueden servir de guía:

http://hojaynumeros.blogspot.com.es/2014/02/numeros-de-pell.html
http://hojaynumeros.blogspot.com.es/2014/01/sucesion-de-jacobsthal.html

Usaremos la misma herramienta de hoja de cálculo, recurre_lineal,  alojada en

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2

Así que enlazaremos con lo ya publicado estudiando la ecuación característica x2-a1x-a2=0 en el caso en el que tenga soluciones enteras.

Es fácil ver que si llamamos Z1 y Za esas dos soluciones, deberá cumplirse que a1=Z1+Z2 y a2=-Z1Z2. Así de simple: si deseas unas soluciones determinadas (aquí enteras) basta que tomes como coeficiente de X(n-1) en la ecuación de recurrencia su suma y como segundo coeficiente su producto cambiado de signo:

X(n)=(Z1+Z2)X(n-1)-Z1Z2X(n-2)

Por ejemplo, si deseamos generar mediante recurrencia X(n)=5n-1n, el primer paso sería elegir como a1 su suma 6 y como  asu producto 5 tomado negativo.

Así de simple: si deseas unas soluciones determinadas (aquí enteras) basta que tomes como coeficiente de X(n-1) en la ecuación de recurrencia su suma y como segundo coeficiente su  su producto 5 tomado negativo:

X(n)=6X(n-1)-5X(n-2)

Los términos iniciales los elegiríamos por sustitución X(0)=50-10=1-1=0 y X(1)= 51-11=5-1=4. Lo volcamos todo en nuestra hoja de cálculo recurre_lineal y obtendremos:



Son los números de fórmula 5n-1 pedidos. Si resolvemos su ecuación característica comprobaremos esta expresión:



Esta sucesión la tienes en http://oeis.org/A024049 En la dirección http://oeis.org/wiki/Index_to_OEIS:_Section_Rec tienes un completo catálogo de sucesiones generadas de forma similar.

Situación inversa

Toda sucesión definida en su término general por X(n)=mAn+nBn (en este caso con m y n enteros) se puede generar de esta forma:

Si X(n)=mAn+nBn y X(n-1)=mAn-1+nBn-1, tendremos X(n+1)=(A+B)*(mAn+nBn)-AB*(mAn-1+nBn-1)= (A+B-B)*mAn+ (A+B-A)*nBn = mAn+1+nBn-1, luego la recurrencia es válida.

Después haríamos X(0)=m+n y X(1)=mA+nB

Toda sucesión del tipo X(n)=mAn+nBn se puede generar mediante una recurrencia lineal homogénea de segundo orden

Otro ejemplo

Tomemos otro ejemplo: X(n)=4n-2n. La recurrencia que la reproduce será: X(0)=0, X(1)=4-2=2, X(n)=6X(n-1)-8X(n-2)

Aquí tienes la sucesión formada con nuestra hoja de cálculo



Hemos elegido la recurrencia propuesta


Y hemos reproducido la diferencia de potencias como fórmula general:



Esta sucesión la tienes estudiada en http://oeis.org/A020522 y medio escondida figura la recurrencia.

De esta forma podemos generar cualquier otra sucesión de ese tipo. Tomemos un ejemplo con un negativo: X(n)=7n-(-2)n. En este caso tomaríamos X(0)=0, X(1)=9, X(n)=5X(n-1)+14X(n-2). En la imagen puedes estudiar la comprobación:



Función generatriz

Si una sucesión está definida como combinación lineal de potencias de dos enteros hemos demostrado que se puede generar mediante una recurrencia de segundo orden. Podremos usar el modelo de F.G. que definimos en su momento


En este caso se traduciría así:


En el ejemplo anterior se traduciría como


Lo comprobamos con PARI

{print(taylor(9*x/(1-5*x-14*x^2), x,12))}

Efectivamente, los coeficientes del desarrollo coinciden con los obtenidos con hoja de cálculo.

9*x + 45*x^2 + 351*x^3 + 2385*x^4 + 16839*x^5 + 117585*x^6 + 823671*x^7 + 5764545*x^8 + 40354119*x^9 + 282474225*x^10 + 1977328791*x^11 + O(x^12)

Números de Mersenne

Los números de forma 2n-1 son llamados “de Mersenne”, aunque son más populares los “primos de Mersenne” 3, 7, 31, 127, 8191, 131071,…Con lo explicado anteriormente será fácil generarlos:

 a1=3, a2=-2, X(0)=0, X(1)=1. Volcamos estos datos en la herramienta:



Obtenemos



Comprobamos la expresión general:



Estos números los encontrarás en http://oeis.org/A000225 Merece la pena que recorras los comentarios sobre esta sucesión, en especial su conexión con el problema de las torres de Hanoi.

En el apartado de fórmulas encontrarás la recurrencia que hemos usado y la función generatriz, que puedes comprobar con lo explicado anteriormente.

Una suma de potencias

¿Cómo engendrar mediante recurrencia la sucesión 2n+3n?

Te dejamos tan sólo el volcado de pantalla de la misma, para que saques tus consecuencias: