Recurrencias lineales de segundo orden

En este blog no hemos tratado mucho las relaciones de recurrencia. Iniciamos ahora el estudio de un caso particular de las mismas, más por los casos curiosos que presenta que por su estudio teórico, que se puede desarrollar mejor en otras publicaciones, como
(http://mathworld.wolfram.com/LinearRecurrenceEquation.html)

Llamaremos relación de recurrencia lineal de segundo orden a la que existe  entre los términos de una sucesión si reviste esta forma:

Interpretamos que cada término a partir uno de ellos equivale al anterior multiplicado por un número más el anterior del anterior por otro y sumado un tercer número. Como hemos indicado que nuestras pretensiones no son teóricas, nos dedicaremos tan sólo al caso en el que a₃=0, es decir, a relaciones lineales de segundo orden homogéneas, pues en ellas encontraremos bastantes hechos curiosos.

Lo normal es definir directamente los primeros términos, llamados valores iniciales, y después dar los coeficientes de la recurrencia, que supondremos constantes.

Por ejemplo, en la sucesión de Fibonacci, definimos directamente x₀=1, x₁=1 y usamos los coeficientes a₁=1 y a₂=1, con lo que la relación de recurrencia vendrá dada por x_n=x_n-1+x_n-2, constituyendo una recurrencia lineal de segundo orden homogénea, y entrando así en nuestro estudio.

Una sucesión definida por recurrencia vendrá dada así por el conjunto de valores iniciales y el de coeficientes, siendo conveniente fijar también el número de términos. Así se concreta, por ejemplo, en Mathematica, la función LinearRecurrence, y así lo trataremos más adelante.

Estas sucesiones reciben el nombre de “sucesiones de Horadam” y se caracterizan por estar determinadas por esos cuatro parámetros dentro de una recurrencia de segundo orden homogénea. Así, la sucesión de Fibonacci es Horadam(0,1,1,1), porque los parámetros se escriben en orden inverso a como lo hacemos aquí. Sólo estudiaremos algunos casos, pues el tema es muy amplio y con muchas sucesiones interesantes.

Generación con hoja de cálculo

Aprovechando la recursividad del Basic de las hojas de cálculo se pueden definir funciones que devuelvan el valor de x(n). El problema que tienen es que funcionan mientras no se llene la pila de datos (ver http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html). En este caso podrían tener esta estructura:

Public Function recurre(c1, c2, d1, d2, n)
Dim r
If n = 0 Then
r = d1
ElseIf n = 1 Then
r = d2
Else
r = c1 * recurre(c1, c2, d1, d2, n - 1) + c2 * recurre(c1, c2, d1, d2, n - 2)
End If
recurre = r
End Function

La tienes implementada en la hoja recurre_lineal, que ofrecemos en

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

Para evitar el problema del llenado de la pila de recursividad, hemos preparado un generador muy simple de estas sucesiones, en la hoja mencionada, con el que practicaremos algunos conceptos y que no usa la recursividad para evitar ese problema:

Basta estudiar la imagen para entender que hay que escribir el número de términos, los coeficientes, aquí llamados A y B y  los valores iniciales. Para fijar ideas, generaremos los números de Pell, dados por la ecuación x_n=2x_n-1+x_n-2 con las condiciones iniciales x₀=0 y x₁=1. Todos ellos se pueden identificar en la imagen:

Con el botón Ver sucesión generamos los 20 primeros términos, que están ya publicados en http://oeis.org/A000129 y se nos indica que son los denominadores del desarrollo de los convergentes a raíz de 2 mediante fracciones continuas. Les dedicaremos una entrada próximamente.

Tenemos así una herramienta muy simple para inventarnos sucesiones, independientemente de su importancia matemática. Por ejemplo, llamaremos sucesión “sorpresa” a la engendrada mediante A=2, B=-1, X₀=0, X₁=1. Te dejamos que averigües su desarrollo y en qué consiste la sorpresa.

Ecuación característica

Existe un procedimiento simple para intentar expresar X(n) en función de n en sucesiones definidas por recurrencias de segundo orden: la ecuación característica. Puedes estudiarla en cualquier manual o página web específica, como

http://people.uncw.edu/tompkinsj/133/recursion/homogeneous.htm

 En esencia este método consiste en:

(1) Dada la relación

 planteamos la ecuación de segundo grado

(2) Si las soluciones de esa ecuación son distintas, x1 y x2, la expresión buscada será

o bien una combinación lineal de ambas:

Las soluciones pueden ser reales o complejas.

(3) Si las soluciones de esa ecuación son dobles e iguales a x₁  la expresión buscada será

  o bien una combinación lineal de ambas

(4) En ambos casos, los coeficientes C₁ y C₂ se calcularán a partir de los valores iniciales.
La herramienta que ofrecemos plantea y resuelve la ecuación característica de la sucesión que definamos. En el desarrollo de la fórmula general de x(n) no se ha desarrollado el caso de raíces complejas, ya que no compensaba el trabajo en una programación complicada,  dado que nuestras pretensiones son meramente divulgativas.

Se comienza calculando el discriminante para ver si es el caso de raíz doble o no. Después se encuentran las soluciones de la ecuación característica y en el caso real se escribe la expresión general de x(n). En la imagen se observa la solución para la sucesión que llamamos “sorpresa”, que resulta representar la sucesión de números naturales. Si simplificas la expresión de abajo resulta ser x(n)=n.

Valores según la expresión general

Por último, en el caso de raíces reales, se ofrece una calculadora de los valores de x(n) dado el valor de n. En la imagen puedes ver el cálculo del término 21 de la sucesión de Fibonacci, que resulta tener el valor de 17711.

Hasta aquí las definiciones y la presentación de la herramienta implementada en hoja de cálculo. Recordaremos ahora cómo es su función generatriz antes de pasar al estudio de sucesiones particulares.


Función generatriz

No es difícil encontrar la función generatriz en este caso

(http://hojaynumeros.blogspot.com.es/2013/03/funciones-generatrices-en-combinatoria.html
y
 http://eliatron.blogspot.com.es/2009/01/sucesiones-recurrentes-funciones.html).

Siguiendo el procedimiento explicado en el blog de Tito Eliatron, bastará aplicar lo siguiente:

Si representamos la sucesión por x₀, x₁, x₂, x₃, x₄, …, su F.G. se construirá tomándolos como coeficientes de un polinomio:

Sumando miembro a miembro

Todos los paréntesis son nulos por la definición de la congruencia. Despejando F(x) tendremos:

Por ejemplo, en la sucesión de Fibonacci, si la hacemos comenzar por 0, tendríamos x0=0, x1=1, a1=1, a2=1 y nos daría

Usaremos esta expresión en las siguientes sucesiones que estudiemos. Hasta aquí la primera entrada sobre este tema. Más adelante, alternando con entradas de otras temáticas, iremos presentando casos particulares interesantes.