SUCESIONES RECURSIVAS LINEALES

Juan Sabia Susana Tesauri

1. Introducción

Una forma usual de definir sucesiones de números es inductivamente. Por ejemplo, si alguien conoce la sucesión de Fibonacci, es probable que la recuerde como la sucesión de enteros {f_{n}}_{n∈IN} que cumple

\{ \begin{matrix}f_{1} = 1 \\ f_{2} = 1 \\ f_{n+2} = f_{n} + f_{n+1} & ∀ n ∈ IN \end{matrix}  (1)

y no como la sucesión definida por

f_{n} = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n}  ∀ n ∈ IN  (2)

Sin embargo, (2) da la fórmula exacta de cualquier término de la sucesión de Fibonacci y, en algunas situaciones, esto puede ser más útil que conocer la definición (1). Por ejemplo, a partir de (2), tenemos una expresión para f_{1000} sin necesidad de conocer los 999 términos anteriores y, en general, de esta forma se puede estimar el orden de f_{n}: para esta sucesión,

lim_{n→∞} ( \frac{f_{n}}{\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{n}} ) = 1 y por lo tanto se deduce que su crecimiento es exponencial.

Más adelante veremos como se usa (2) para acotar la cantidad de pasos del algoritmo de Euclides para números naturales.

Aplicando inducción se puede demostrar que las sucesiones definidas por (1) y por (2) coinciden, pero ¿cómo obtener la fórmula (2) a partir de (1)?

Este problema no es arbitrario: en muchos contextos aparecen sucesiones definidas en forma inductiva y no por medio de la fórmula explícita del término n-ésimo. Analicemos, por ejemplo, el siguiente caso:

Queremos diseñar un algoritmo que pueda triangular cualquier matriz cuadrada en IR^{n×n} y nos interesa contar la cantidad máxima de operaciones (+, −, ×, ÷) necesarias para hacerlo (no se contarán las comparaciones ni los cambios de lugar de coeficientes). Para cada n ∈ IN tendremos entonces un número x_{n} que cuenta la cantidad máxima de operaciones necesarias para triangular una matriz de n × n y esto define una sucesión {x_{n}}_{n∈IN}. Si tomamos como algoritmo el método de Gauss, podemos observar las siguientes propiedades de la sucesión {x_{n}}_{n∈IN}:

(i) x_{1} = 0 (una matriz de 1 × 1 ya está triangulada)

(ii) Dada la matriz A = (a_{ij}) ∈ IR^{n×n}, podemos suponer que a_{11} ≠ 0 (si fuese cero, podemos elegir algún elemento a_{i1} ≠ 0 (2 ≤ i ≤ n) e intercambiar la fila i con la fila 1; en el caso en que sean todos cero, nuestro problema se reduce a triangular una matriz de (n − 1) × (n − 1)). Para lograr un cero en el lugar que ocupa a_{21} hay que multiplicar la primer fila por \frac{a_{21}}{a_{11}} y restársela a la segunda fila.

¿Cuántas operaciones se realizan? Hay una división (\frac{a_{21}}{a_{11}} ), (n − 1) multiplicaciones y (n − 1) restas (como ya sabemos que en el primer lugar de la fila va a ir un cero, no nos tomamos el trabajo de hacer la cuenta a_{21} − (\frac{a_{21}}{a_{11}} ).a_{11}). Este procedimiento lo tenemos que repetir (n − 1) veces para obtener ceros en los primeros lugares de las todas las filas i (2 ≤ i ≤ n). Y ahora sólo nos resta triangular una matriz de (n − 1) × (n − 1). Por lo tanto, tenemos que

x_{n} = (n − 1)(2(n − 1) + 1) + x_{n−1} ∀ n ∈ IN, n ≥ 2

Es decir, haciendo un cambio de variables, la sucesión {x_{n}}_{n∈IN} queda definida por la recursión:

\{ \begin{matrix}x_{1} = 0 \\ x_{n+1} = (2n^{2} + n) + x_{n} & ∀ n ∈ IN \end{matrix}

Sin embargo, de esta forma, por ejemplo, no podemos estimar cuántas operaciones serán necesarias para triangular una matriz de n×n por medio de este algoritmo sin antes calcular cuántas serán necesarias para triangular matrices de menor tamaño. Si conociésemos para cierta computadora el tiempo que tarda en llevarse a cabo cada operación, con la fórmula cerrada de la sucesión {x_{n}}_{n∈IN} , podríamos estimar a priori el tiempo que tardaría en efectuarse la triangulación de una matriz de n × n.

La intención de estas notas es exhibir un método para encontrar una forma cerrada o fórmula general para el término n-ésimo (es decir, una fórmula que no dependa de los términos anteriores) de ciertas sucesiones definidas por recurrencia. Este método se basa en técnicas elementales de Algebra Lineal.

2. Definiciones y ejemplos

Primero, definamos el tipo de sucesiones con las que vamos a trabajar. Para no tener que considerar restricciones, consideraremos sucesiones de números complejos y al conjunto de todas estas sucesiones lo notaremos C^{IN}. Definición: Una sucesión {x_{n}}_{n∈IN} ∈ C^{IN} se dice recursiva lineal de orden menor o igual que k si existen k números complejos α_{0}, α_{1},…, α_{k−1} tales que

x_{n+k} = α_{0}.x_{n} + α_{1}.x_{n+1} + ⋯ + α_{k−1}.x_{n+k−1} ∀ n ∈ IN

Es decir, una sucesión {x_{n}}_{n∈IN} será recursiva lineal de orden menor o igual que k cuando, dados los primeros k elementos, el (k + 1)-ésimo y todos los siguientes se pueden calcular haciendo una combinación lineal fija de los k anteriores.

Analicemos ahora algunos ejemplos:

Ejemplo 1: Consideremos todas las posibles sucesiones recursivas lineales de orden menor o igual que 1. Necesariamente, la definición será (para algún a y algún λ en C):

\{ \begin{matrix}x_{1} = a \\ x_{n+1} = λ.x_{n} \end{matrix}

En este caso, es muy fácil conjeturar el término general de la sucesión y probar que

x_{n} = a.λ^{n−1} ∀ n ∈ IN

si λ ≠ 0. Para no tener que distinguir casos, por convención consideraremos 0^{0} = 1. Esta sucesión se llama la sucesión geométrica de primer término a y razón λ. Notación: Llamamos G_{λ} a la sucesión geométrica de razón λ cuyo primer término es 1.

En el próximo ejemplo, veremos por qué no se puede definir directamente la noción exacta de orden: Ejemplo 2: Consideremos, dados a y λ complejos, la siguiente sucesión recursiva lineal:

\{ \begin{matrix}x_{1} = a \\ x_{2} = λ.a \\ x_{n+2} = λ^{2}.x_{n} \end{matrix}

Es inmediato ver que esta sucesión es la geométrica de primer término a y razón λ. Según esta definición, su orden es menor o igual que 2 y según la definición dada en el Ejemplo 1 su orden es menor o igual que 1. Es decir, como una sucesión recursiva lineal puede definirse de distintas maneras, no se puede dar una noción exacta del orden que dependa de una sola de estas definiciones . Lo único que se puede afirmar es que el orden será menor o igual que cierto número natural. Ahora estamos en condiciones de precisar el concepto de orden:

Definición: Sea {x_{n}}_{n∈IN} ∈ C^{IN} una sucesión recursiva lineal. Se define el orden de {x_{n}}_{n∈IN} (y se lo nota ord({x_{n}}_{n∈IN})) como el número natural:

i) 1 si {x_{n}}_{n∈IN} es una sucesión recursiva lineal de orden menor o igual que 1, es decir, si {x_{n}}_{n∈IN} es una sucesión geométrica. ii) k si {x_{n}}_{n∈IN} es una sucesión recursiva lineal de orden menor o igual que k pero no es una sucesión recursiva lineal de orden menor o igual que (k − 1).

La definición de orden nos asegura que, si {x_{n}}_{n∈IN} es una sucesión recursiva lineal de orden k, todo elemento a partir del (k + 1)-ésimo se puede escribir como una combinación lineal fija de los k elementos anteriores, pero que esto no puede hacerse a partir del término k-ésimo usando solamente los (k − 1) términos anteriores.

Sigamos ahora con algunos ejemplos y calculemos en cada caso el orden. Ejemplo 3: Dada la sucesión aritmética de primer término a y razón λ, es decir, la sucesión {x_{n}}_{n∈IN} definida por:

\{ \begin{matrix}x_{1} = a \\ x_{n+1} = λ + x_{n} & ∀ n ∈ IN \end{matrix}

intentaremos ver si es recursiva lineal. Es evidente que, a menos que λ = 0 (en cuyo caso la sucesión coincide con la geométrica de primer término a y razón 1), esta definición no nos sirve para decidir si es recursiva lineal o no así que trataremos de modificarla. Consideremos dos términos consecutivos:

\begin{aligned}x_{n+1} & = λ + x_{n} \\ x_{n+2} & = λ + x_{n+1} \end{aligned}

Si restamos miembro a miembro las desigualdades anteriores, obtenemos

x_{n+2} = 2x_{n+1} − x_{n} ∀ n ∈ IN

lo que nos permite afirmar que la sucesión {x_{n}}_{n∈IN} es recursiva lineal de orden menor o igual que 2:

\{ \begin{matrix}x_{1} = a \\ x_{2} = a + λ \\ x_{n+2} = 2x_{n+1} − x_{n} & ∀ n ∈ IN \end{matrix}

Para calcular el orden, consideremos que λ ≠ 0. En este caso, la sucesión no es constante a partir de ningún término. Si su orden fuese 1, sería geométrica, ninguno de sus términos podría ser cero (porque, de suceder esto, la sucesión se haría constante a partir de allí) y la razón sería la división entre dos términos consecutivos. Por ejemplo, entre x_{3} y x_{2} ó entre x_{2} y x_{1}:

\frac{a + 2λ}{a + λ} = \frac{a + λ}{a}

luego

a^{2} + 2λa = a^{2} + 2λa + λ^{2}

y, por lo tanto, λ = 0 lo que es un absurdo. Entonces, si λ ≠ 0, el orden de esta sucesión es 2.

Ejemplo 4: La sucesión de Fibonacci {f_{n}}_{n∈IN} (ver (1)) es evidentemente recursiva lineal. De la definición, se deduce que el orden es menor o igual que 2. Si fuese menor o igual que 1, la sucesión de Fibonacci sería geométrica, pero como f_{1} = 1 y f_{2} = 1, tendría que ser la sucesión G_{1} constante. Como f_{3} = 2 ≠ 1, no tiene orden menor o igual que 1 y por lo tanto, ord ({f_{n}}_{n∈IN}) = 2.

Ejemplo 5: Consideremos la sucesión periódica

(1, 3, 5, 1, 3, 5, 1, 3, 5, 1, 3, 5, 1, 3, 5, ...)

Una posible definición por recurrencia será:

\{ \begin{matrix}x_{1} = 1 \\ x_{2} = 3 \\ x_{3} = 5 \\ x_{n+3} = x_{n} & ∀ n ∈ IN \end{matrix}

Su orden es menor o igual que 3. Si fuese menor o igual que 2, existirían a y b complejos tales que la sucesión podría definirse por

\{ \begin{matrix}x_{1} = 1 \\ x_{2} = 3 \\ x_{n+2} = a.x_{n+1} + b.x_{n} & ∀ n ∈ IN \end{matrix}

Considerando los términos x_{3}, x_{4} y x_{5}, se tendría:

\{ \begin{matrix}5 = a.3 + b.1 \\ 1 = a.5 + b.3 \\ 3 = a.1 + b.5 \end{matrix}

pero este sistema lineal no tiene soluciones, es decir no existen tales a y b. Por lo tanto, la sucesión tiene orden 3.

Ejemplo 6: La sucesión cuyo término n-ésimo cuenta la cantidad máxima de operaciones del algoritmo de Gauss para triangular una matriz de n × n es (ver Introducción):

\{ \begin{matrix}x_{1} = 0 \\ x_{n+1} = (2n^{2} + n) + x_{n} & ∀ n ∈ IN \end{matrix}

¿Será esta una sucesión recursiva lineal?

Consideremos, para todo n ∈ IN los términos x_{n+1}, x_{n+2}, x_{n+3} y x_{n+4} de la sucesión:

\begin{aligned}x_{n+1} & = (2n^{2} + n) + x_{n} \\ x_{n+2} & = (2n^{2} + 5n + 3) + x_{n+1} \\ x_{n+3} & = (2n^{2} + 9n + 10) + x_{n+2} \\ x_{n+4} & = (2n^{2} + 13n + 21) + x_{n+3} \end{aligned}  (3)

Podemos pensar las expresiones (2n^{2} +n), (2n^{2} +5n+3), (2n^{2} +9n+10) y (2n^{2} +13n+21) que aparecen en las igualdades como polinomios en n de grado 2. Pero cuatro polinomios de grado 2 son necesariamente dependientes, es decir, existe una combinación lineal no trivial de ellos que da el polinomio 0. Planteando las cuentas correspondientes se obtiene que

(−1)(2n^{2} + n) + 3(2n^{2} + 5n + 3) − 3(2n^{2} + 9n + 10) + 1(2n^{2} + 13n + 21) = 0

Aplicando la misma combinación lineal a las ecuaciones (3) miembro a miembro, resulta

(−1)x_{n+1} + 3x_{n+2} − 3x_{n+3} + x_{n+4} = (−1)x_{n} + 3x_{n+1} − 3x_{n+2} + x_{n+3}

y, por lo tanto, la sucesión analizada cumple

x_{n+4} = 4x_{n+3} − 6x_{n+2} + 4x_{n+1} − 1x_{n} ∀ n ∈ IN

Es decir, la sucesión está definida por

\{ \begin{matrix}x_{1} = 0 \\ x_{2} = 3 \\ x_{3} = 13 \\ x_{4} = 34 \\ x_{n+4} = 4x_{n+3} − 6x_{n+2} + 4x_{n+1} − 1x_{n}  ∀ n ∈ IN \end{matrix}

lo que dice que es recursiva lineal de orden menor o igual que cuatro. Puede probarse (ejercicio a cargo del lector) que el orden es exactamente cuatro planteando la posibilidad de que sea recursiva lineal de orden menor o igual que tres y llegando a un absurdo.

En los próximos dos ejemplos, probaremos que ciertas sucesiones no son recursivas lineales para ilustrar el tipo de dificultad que puede aparecer. Ejemplo 7: La sucesión {2^{2^{n}}}_{n∈IN} no es recursiva lineal. Supongamos que sí lo es. Existen entonces k ∈ IN y α_{0},…, α_{k−1} números complejos tales que

2^{2^{n+k}} = ∑_{0≤i≤k−1} α_{i}2^{2^{n+i}} ∀ n ∈ IN

Sea C = max{|α_{i}| / 0 ≤ i ≤ k − 1} y consideremos el módulo de la expresión anterior. Entonces

2^{2^{n+k}} = | ∑_{0≤i≤k−1} α_{i}2^{2^{n+i}}| ≤ ∑_{0≤i≤k−1} |α_{i}|2^{2^{n+i}} ≤ ∑_{0≤i≤k−1} C2^{2^{n+k−1}} = kC2^{2^{n+k−1}}

Por lo tanto, tenemos que

2^{2^{n+k−1}} = \frac{2^{2^{n+k}}}{2^{2^{n+k−1}}} ≤ kC ∀ n ∈ IN

pero esto es absurdo ya que el primer miembro es una sucesión que tiende a infinito y, por lo tanto, no puede estar acotado.

Ejemplo 8: Consideremos la sucesión {log n}_{n∈IN} y supongamos que es recursiva lineal de orden menor o igual que k para algún k ∈ IN fijo. Entonces existirán números complejos α_{0}, α_{1},…, α_{k−1} tales que

log(n + k) = α_{0} log(n) + α_{1} log(n + 1) + … + α_{k−1} log(n + k − 1) ∀ n ∈ IN

Tomando parte real de ambos lados de la igualdad, se obtiene una ecuación de recurrencia a coeficientes reales. Luego, sin pérdida de generalidad, podemos suponer que α_{0}, α_{1},…, α_{k−1} son números reales. Consideremos la función f : IR_{>0} → IR definida por

f(x) = log(x + k) − α_{0} log(x) − α_{1} log(x + 1) −… − α_{k−1} log(x + k − 1)

f es continua y derivable en (0, +∞) y f(n) = 0 ∀ n ∈ IN. Por lo tanto, usando el Teorema de Rolle, su derivada f′ vale cero en infinitos puntos. Calculando f′ se obtiene

f′(x) = \frac{1}{x + k} − α_{0} \frac{1}{x} − α_{1} \frac{1}{x + 1} −… − α_{k−1} \frac{1}{x + k − 1}

y operando

f′(x) = \frac{∏_{0≤i≤k}(x + i) − α_{0} ∏_{1≤i≤k+1}(x + i) −… − α_{k−1} ∏_{{0≤i≤k+1 \atop i≠k}}(x + i)}{∏_{0≤i≤k+1}(x + i)}

Como f′ vale cero en infinitos puntos, el numerador es un polinomio que tiene infinitas raíces y por lo tanto debe ser el polinomio nulo. Sin embargo, cuando evaluamos el numerador en (−k − 1), obtenemos ∏_{0≤i≤k}(−k − 1 + i) que es un número distinto de cero.

Esto es una contradicción que proviene del hecho de suponer que la sucesión (log n)_{n∈IN} es recursiva lineal.

Para terminar con esta sección, probaremos una propiedad sobre la sucesión suma de una sucesión recursiva lineal:

Proposición. Sea {x_{n}}_{n∈IN} una sucesión recursiva lineal de orden k y sea {S_{n}}_{n∈IN} la sucesión definida por

S_{n} = ∑_{1≤i≤n} x_{i} ∀ n ∈ IN

Entonces {S_{n}}_{n∈IN} es una sucesión recursiva lineal de orden menor o igual que k + 1.

Demostración: Consideremos la definición por recurrencia de {x_{n}}_{n∈IN} :

x_{n+k} = α_{0}.x_{n} + α_{1}.x_{n+1} + ⋯ + α_{k−1}.x_{n+k−1} ∀ n ∈ IN

En particular, reemplazando n por n + 1, vale

x_{n+1+k} = α_{0}.x_{n+1} + α_{1}.x_{n+2} + ⋯ + α_{k−1}.x_{n+k} ∀ n ∈ IN

Pero como x_{n+1} = S_{n+1} − S_{n} ∀ n ∈ IN, reemplazando y despejando S_{n+1+k}, se tiene que

S_{n+1+k} = α_{0}.(S_{n+1} − S_{n}) + ⋯ + α_{k−1}.(S_{n+k} − S_{n+k−1}) − S_{n+k} ∀ n ∈ IN.

Si reagrupamos y sumamos los términos del segundo miembro, nos da la recurrencia de orden menor o igual que k + 1 buscada.

Ejercicios

Ejercicio 1. Decidir cuáles de las siguientes sucesiones {a_{n}}_{n∈ IN} son recursivas lineales. En caso afirmativo hallar una ecuación de recurrencia y el orden.

i) a_{n} = 3^{n} + n.3^{n−1} ii) a_{n} = \frac{1}{n} iii) a_{n} = (3^{n} + n.3^{n−1})(5^{n} − n.5^{n−1}) iv) a_{n} = n^{2}

iv) a_{n} = ∑_{1≤i≤n} n^{3}

Ejercicio 2. Sea {x_{n}}_{n∈IN} una sucesión de números reales positivos creciente. Probar que, si es recursiva lineal, existe una constante C tal que

\frac{x_{n+1}}{x_{n}} ≤ C ∀ n ∈ IN

¿Vale la recíproca?

Ejercicio 3.

i) Sean a_{1},…, a_{k}, a ∈ C. Se considera la siguiente sucesión:

\{ \begin{matrix}x_{1} , …, x_{k} \\ x_{n+k} = ∑_{i=0}^{k−1} a_{i}.x_{n+i} + a & si n ≥ 1 \end{matrix}

Probar que {x_{i}}_{i∈ IN} es una sucesión recursiva lineal. ¿Qué se puede decir del orden? ii) Sean a_{1},…, a_{k} ∈ C y sea {x_{n}}_{n∈ IN} una sucesión recursiva lineal. Probar que la sucesión

\{ \begin{matrix}y_{1} = a_{1} , …, y_{k} = a_{k} \\ y_{k+n} = x_{n} & si n ≥ 1 \end{matrix}

es recursiva lineal. ¿Qué se puede decir del orden?

Ejercicio 4. Sea P ∈ C [X] un polinomio de grado k. Probar que la sucesión {x_{n}}_{n∈IN} definida por

x_{n} = P (n) ∀n ∈ IN

es recursiva lineal de orden menor o igual que k + 1.

Ejercicio 5.

i) Sea S ⊆ C un conjunto finito y sea {x_{n}}_{n∈ IN} una sucesión recursiva lineal tal que x_{i} ∈ S para todo i ∈ IN. Probar que {x_{n}}_{n∈ IN} es periódica a partir de cierto término. ii) Sea \{x_{n}\}_{n∈ IN} la sucesión de los dígitos del desarrollo decimal de \sqrt{2} y sea D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Probar que para ningún valor de k existe f : D^{k} → D tal que f(x_{n}, x_{n+1},…, x_{n+k−1}) = x_{n+k} ∀ n ∈ IN.

3. Estructura del conjunto de sucesiones recursivas lineales

Las sucesiones recursivas lineales forman un subespacio vectorial de C^{IN} pero para probarlo debemos hacer ciertas consideraciones previas.

Definición: Sea P = ∑_{0≤i≤k} α_{i}X^{i} ∈ C[X]−{0} un polinomio de grado k y sea {x_{n}}_{n∈IN} una

sucesión recursiva lineal. Se dice que {x_{n}}_{n∈IN} satisface P si

α_{0}.x_{n} + α_{1}.x_{n+1} + ⋯ + α_{k}.x_{n+k} = 0 ∀ n ∈ IN

Es decir, estamos asociando a la ecuación de recurrencia de la sucesión un polinomio. Por ejemplo, una sucesión geométrica de razón λ satisface los polinomios (X − λ) y (X^{2} − λ^{2}) (ver Ejemplos 1 y 2), cualquier sucesión aritmética satisface el polinomio X^{2} − 2X + 1 (ver Ejemplo 3) y la sucesión de Fibonacci satisface el polinomio (X^{2} − X − 1) (ver Ejemplo 4).

Proposición. Sea P = ∑_{0≤i≤k} α_{i}X^{i} ∈ C[X] − {0} un polinomio de grado k y sea

S_{P} = {{x_{n}}_{n∈IN} ∈ C^{IN} / {x_{n}}_{n∈IN} es una sucesión recursiva lineal que satisface P }. Entonces S_{P} es un C-subespacio vectorial de C ^{IN} de dimensión k.

Demostración: Para probar que S_{P} es un subespacio veremos que contiene a la sucesión {0}_{n∈IN}, que es cerrado para la suma y para el producto por escalares.

i) Es evidente que {0}_{n∈IN} satisface P ya que α_{0}.0 + α_{1}.0 + ⋯ + α_{k}.0 = 0. ii) Sean {x_{n}}_{n∈IN} y {y_{n}}_{n∈IN} en S_{P}. Es decir,

α_{0}.x_{n} + α_{1}.x_{n+1} + ⋯ + α_{k}.x_{n+k} = 0 ∀ n ∈ IN
α_{0}.y_{n} + α_{1}.y_{n+1} + ⋯ + α_{k}.y_{n+k} = 0 ∀ n ∈ IN

Sumando miembro a miembro, se obtiene que {x_{n} + y_{n}}_{n∈IN} ∈ S_{P}. iii) Si {x_{n}}_{n∈IN} ∈ S_{P} y z ∈ C, multiplicando por z la igualdad

α_{0}.x_{n} + α_{1}.x_{n+1} + ⋯ + α_{k}.x_{n+k} = 0 ∀ n ∈ IN

se ve que {z.x_{n}}_{n∈IN} ∈ S_{P}.

Ahora sólo falta ver que tiene dimensión k. Primero, observemos que, fijados k números complejos x_{1},…, x_{k}, existe una única sucesión en S_{P} que tiene a estos k números como sus primeros k términos ordenados (el elemento x_{k+1} será −\frac{α_{0}.x_{1}+α_{1}.x_{2}+···+α_{k−1}.x_{k}}{α_{k}} y, si x_{n},…, x_{n+k−1} están definidos, el elemento x_{n+k} será −\frac{α_{0}.x_{n}+α_{1}.x_{n+1}+···+α_{k−1}.x_{n+k−1}}{α_{k}}). Consideremos ahora la sucesión E_{i} ∈ S_{P} (1 ≤ i ≤ k) que en el lugar j-ésimo (1 ≤ j ≤ k) tiene el elemento (E_{i})_{j} definido de la siguiente forma:

(E_{i})_{j} = \{ \begin{matrix}0 & si i ≠ j \\ 1 & si i = j \end{matrix}

Es decir, si escribimos hasta el término k-ésimo de las sucesiones tenemos

E_{1} = {1, 0,…, 0, 0,…
E_{2} = {0, 1,…, 0, 0,…

…

E_{k} = {0, 0,…, 0, 1,…

Las sucesiones E_{1}, E_{2},…, E_{k} son linealmente independientes: si ∑_{1≤i≤k} β_{i}E_{i} es la

sucesión {0}_{n∈IN}, los primeros k términos deberán ser 0 y por lo tanto, β_{1} = β_{2} = … = β_{k} = 0.

Sea {x_{n}}_{n∈IN} una sucesión en S_{P}. La sucesión ∑_{1≤i≤k} x_{i}E_{i} está en S_{P} (pues es una

combinación lineal de elementos de S_{P}) y sus primeros k términos coinciden con los de {x_{n}}_{n∈IN} , por lo tanto

{x_{n}}_{n∈IN} = ∑_{1≤i≤k} x_{i}E_{i}

Luego {E_{1}, E_{2},…, E_{k}} es un sistema de generadores linealmente independiente de S_{P} con lo que queda probado que su dimensión es k.

El lema siguiente nos permitirá demostrar que el conjunto de todas las sucesiones recursivas lineales es un C-espacio vectorial.

Lema. Sea P = ∑_{0≤i≤k} α_{i}X^{i} ∈ C[X] − {0} un polinomio de grado k y sea {x_{n}}_{n∈IN} una

sucesión recursiva lineal que satisface P. Entonces, para todo Q = ∑_{0≤i≤h} β_{i}X^{i} en

C[X] − {0}, {x_{n}}_{n∈IN} satisface QP.

Demostración: La demostración se hará por pasos: Paso I: Sean P = ∑_{0≤i≤k} α_{i}X^{i} y R = ∑_{0≤i≤j} γ_{i}X^{i} en C[X] − {0} tal que P + R ≠ 0. Si {x_{n}}_{n∈IN} satisface P y R, entonces {x_{n}}_{n∈IN} satisface P + R:

Completando si es necesario con coeficientes nulos podemos suponer que k = j. Entonces

∑_{0≤i≤k} α_{i}x_{n+i} = 0 ∀ n ∈ IN

∑_{0≤i≤k} γ_{i}x_{n+i} = 0 ∀ n ∈ IN

Sumando miembro a miembro las dos desigualdades anteriores, se obtiene lo deseado. Paso II: Sea P = ∑_{0≤i≤k} α_{i}X^{i} en C[X] − {0} y sea a ∈ C − {0}. Si {x_{n}}_{n∈IN} satisface P,

entonces {x_{n}}_{n∈IN} satisface a.P:

Basta multiplicar por a la igualdad

∑_{0≤i≤k} α_{i}x_{n+i} = 0 ∀ n ∈ IN

Paso III: Sea P = ∑_{0≤i≤k} α_{i}X^{i} en C[X]−{0}. Si {x_{n}}_{n∈IN} satisface P, entonces {x_{n}}_{n∈IN} sa-

tisface X^{r}.P para todo r ∈ IN

Teniendo en cuenta que

∑_{0≤i≤k} α_{i}x_{n+i} = 0

vale para todo n ∈ IN, en particular vale para n + r:

∑_{0≤i≤k} α_{i}x_{n+r+i} = 0 ∀ n ∈ IN

y esto quiere decir que {x_{n}}_{n∈IN} satisface X^{r}.P

Ahora, combinando los tres pasos, demostramos el lema: como {x_{n}}_{n∈IN} satisface P, satisface X^{i}.P para todo 0 ≤ i ≤ h y por lo tanto satisface β_{i}.X^{i}.P para todo 0 ≤ i ≤ h. Sumando, obtenemos que {x_{n}}_{n∈IN} satisface ∑_{0≤i≤h} β_{i}.X^{i}.P = Q.P que es lo que queríamos

demostrar.

Ahora estamos en condiciones de demostrar el siguiente

Teorema. El conjunto S ⊂ C^{IN} de todas las sucesiones recursivas lineales es un C-espacio vectorial.

Demostración: Basta demostrar que S es un C-subespacio vectorial de C^{IN} y esto se basará en el Lema anterior:

i) {0}_{n∈IN} ∈ S es evidente. ii) Si {x_{n}}_{n∈IN} ∈ S y {y_{n}}_{n∈IN} ∈ S, eso significa que existen polinomios P y Q en C[X] − {0} tales que {x_{n}}_{n∈IN} satisface P y {y_{n}}_{n∈IN} satisface Q. Pero, por el Lema anterior, {x_{n}}_{n∈IN} satisface P.Q y {y_{n}}_{n∈IN} también satisface P.Q y, como S_{P.Q} es un subespacio de C^{IN}, {x_{n}}_{n∈IN} + {y_{n}}_{n∈IN} debe satisfacer P.Q y por lo tanto será recursiva lineal. iii) Si {x_{n}}_{n∈IN} ∈ S y a ∈ C, existe un polinomio P en C[X]−{0} tal que {x_{n}}_{n∈IN} satisface P. Como S_{P} es un subespacio de C ^{IN}, a.{x_{n}}_{n∈IN} debe satisfacer P y por lo tanto, será recursiva lineal.

4. La fórmula general

Para encontrar una fórmula general del término n-ésimo de una sucesión recursiva lineal {x_{n}}_{n∈IN} , traducimos nuestro problema a una ecuación matricial. Supongamos que

{x_{n}}_{n∈IN} satisface un polinomio P ∈ C[X], P = X^{k} − ∑_{i=0}^{k−1} α_{i}.X^{i}. Es decir, para todo

n ∈ IN, x_{n+k} = ∑_{i=0}^{k−1} α_{i}.x_{n+i}. En notación matricial, podemos escribir:

( \begin{matrix}0 & 1 & 0 & 0 & … & 0 \\ 0 & 0 & 1 & 0 & … & 0 \\ 0 & 0 & 0 & 1 & … & 0 \\ … & … & … & … & … & … \\ 0 & 0 & 0 & 0 & … & 1 \\ α_{0} & α_{1} & α_{2} & α_{3} & … & α_{k−1} \end{matrix} ) . ( x_{n} ; x_{n+1} ; x_{n+2} ; ⋮ ; x_{n+k−2} ; x_{n+k−1} ) = ( x_{n+1} ; x_{n+2} ; x_{n+3} ; ⋮ ; x_{n+k−1} ; x_{n+k} ) ∀ n ∈ IN

y más generalmente, si notamos con C_{P} a la matriz

C_{P} = ( \begin{matrix}0 & 1 & 0 & 0 & … & 0 \\ 0 & 0 & 1 & 0 & … & 0 \\ 0 & 0 & 0 & 1 & … & 0 \\ … & … & … & … & … & … \\ 0 & 0 & 0 & 0 & … & 1 \\ α_{0} & α_{1} & α_{2} & α_{3} & … & α_{k−1} \end{matrix} )

tendremos que

(C_{P})^{j}. ( x_{1} ; x_{2} ; x_{3} ; ⋮ ; x_{k} ) = ( x_{j+1} ; x_{j+2} ; x_{j+3} ; ⋮ ; x_{j+k} ) ∀ j ∈ IN

Por lo tanto, tomando j + 1 = n, tendremos que el término n-ésimo de la sucesión {x_{n}}_{n∈IN} será una combinación lineal de los coeficientes de (C_{P})^{n−1}. Nuestro problema se reduce, por lo tanto, a encontrar una fórmula para las potencias de la matriz C_{P}. Para eso, consideraremos primero, un caso particular:

4.1. El caso de las raíces simples:

Supongamos que el polinomio P tiene todas sus raíces simples. Como la matriz C_{P} tiene a P como polinomio característico (notar que C_{P} es la matriz compañera del polinomio P), la matriz C_{P} resulta diagonalizable. Es decir, si λ_{1},… λ_{k} son las raíces de P en C, existe una matriz D ∈ C^{k×k} inversible tal que:

D.C_{P} .D^{−1} = ( \begin{matrix}λ_{1} & 0 & 0 & … & 0 \\ 0 & λ_{2} & 0 & … & 0 \\ 0 & 0 & λ_{3} & … & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & λ_{k} \end{matrix} )

y por lo tanto, usando la convención 0^{0} = 1 si es necesario,

(C_{P})^{n−1} = D^{−1}. ( \begin{matrix}λ_{1}^{n−1} & 0 & 0 & … & 0 \\ 0 & λ_{2}^{n−1} & 0 & … & 0 \\ 0 & 0 & λ_{3}^{n−1} & … & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & λ_{k}^{n−1} \end{matrix} ) .D ∀ n ∈ IN

Es decir, los coeficientes de (C_{P})^{n−1} serán combinaciones lineales de λ_{1}^{n−1}, λ_{2}^{n−1},…, λ_{k}^{n−1} y por lo tanto el término n-ésimo de la sucesión {x_{n}}_{n∈IN} también será una combinación lineal de λ_{1}^{n−1}, λ_{2}^{n−1},…, λ_{k}^{n−1}, con lo que queda demostrada la siguiente

Proposición. Sea {x_{n}}_{n∈IN} una sucesión recursiva lineal que satisface un polinomio P ∈ C[X] de grado k cuyas raíces λ_{1}, λ_{2},…, λ_{k} son todas distintas. Entonces existen a_{1}, a_{2},…, a_{k} ∈ C tales que

x_{n} = a_{1}.λ_{1}^{n−1} + a_{2}.λ_{2}^{n−1} + … + a_{k}.λ_{k}^{n−1} ∀ n ∈ IN Observación: Notar que la Proposición anterior asegura que, dado que la dimensión de S_{P} es k, {G_{λ_{1}}, G_{λ_{2}},…, G_{λ_{k}}} es una base de S_{P}.

Ahora utilizaremos esta Proposición para encontrar una fórmula general de algunas sucesiones que ya vimos.

Consideremos la sucesión periódica {x_{n}}_{n∈IN} (Ejemplo 5) definida por

\{ \begin{matrix}x_{1} = 1 \\ x_{2} = 3 \\ x_{3} = 5 \\ x_{n+3} = x_{n} & ∀ n ∈ IN \end{matrix}

Esta sucesión satisface el polinomio P = X^{3} − 1 y, por lo tanto, usando la Proposición anterior, deben existir a, b y c tales que

x_{n} = a.1 + b. (\frac{−1 + i\sqrt{3}}{2})^{n−1} + c. (\frac{−1 − i\sqrt{3}}{2})^{n−1} ∀ n ∈ IN

Teniendo en cuenta las igualdades para n = 1, n = 2 y n = 3, se obtiene

\{ \begin{matrix}a + b + c = 1 \\ a + b. (\frac{−1+i\sqrt{3}}{2}) + c. (\frac{−1−i\sqrt{3}}{2}) = 3 \\ a + b. (\frac{−1−i\sqrt{3}}{2}) + c. (\frac{−1+i\sqrt{3}}{2}) = 5 \end{matrix}

y, resolviendo el sistema se obtiene que a = 3, b = −1 + i\frac{\sqrt{3}}{3} y c = −1 − i\frac{\sqrt{3}}{3}. Es decir

x_{n} = 3+(−1 + i\frac{\sqrt{3}}{3}) . (\frac{−1 + i\sqrt{3}}{2})^{n−1}+(−1 − i\frac{\sqrt{3}}{3}) . (\frac{−1 − i\sqrt{3}}{2})^{n−1} ∀ n ∈ IN

Consideremos ahora la sucesión de Fibonacci {f_{n}}_{n∈IN} (Ejemplo 4) definida por

\{ \begin{matrix}f_{1} = 1 \\ f_{2} = 1 \\ f_{n+2} = f_{n} + f_{n+1} & ∀ n ∈ IN \end{matrix}

Esta sucesión satisface el polinomio P = X^{2} −X −1 que tiene por raíces a \frac{1+\sqrt{5}}{2} y a \frac{1−\sqrt{5}}{2}. Por lo tanto, existen a y b tales que

f_{n} = a. (\frac{1 + \sqrt{5}}{2})^{n−1} + b. (\frac{1 + \sqrt{5}}{2})^{n−1} ∀ n ∈ IN

Como f_{1} = 1 y f_{2} = 1, tenemos que
\{ \begin{matrix}a + b = 1 \\ a. (\frac{1+\sqrt{5}}{2}) + b. (\frac{1−\sqrt{5}}{2}) = 1 \end{matrix}

de donde a = \frac{1}{\sqrt{5}}. (\frac{1+\sqrt{5}}{2}) y b = −\frac{1}{\sqrt{5}}. (\frac{1−\sqrt{5}}{2}) con lo que

f_{n} = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n} ∀ n ∈ IN

Aplicación: Sean a y b números naturales. Queremos estimar la cantidad de divisiones necesarias para calcular el máximo común divisor entre a y b mediante el algoritmo de Euclides.

Lema: Sean a ≤ b números naturales. Consideramos que el algoritmo de Euclides siempre comienza dividiendo el mayor número por el menor. Si f_{n} ≤ a < f_{n+1} (donde f_{i} es el iésimo número de Fibonacci), la cantidad de divisiones necesarias para efectuar el algoritmo de Euclides está acotada por n.

Demostración: Lo demostraremos por inducción en n. Si n = 1 ó n = 2 el resultado es obvio. Supongamos n > 2. Como f_{n} ≤ a < f_{n+1}, el resto r de la división de b por a es menor que f_{n+1}. Pueden darse dos casos.

i) r < f_{n}, en cuyo caso el algoritmo de Euclides entre a y r involucra a lo sumo n − 1 divisiones (por hipótesis inductiva) y por lo tanto, entre a y b involucra a lo sumo n divisiones como queríamos demostrar. ii) f_{n} ≤ r < a < f_{n+1}. En este caso, el siguiente paso será dividir a a por r. Si llamamos q al cociente y r′ al resto, tenemos que:

r′ = a − r.q ≤ a − r < f_{n+1} − f_{n} = f_{n−1}

Luego, el algoritmo de Euclides entre r y r′ involucra a lo sumo n − 2 divisiones (por hipótesis inductiva) y por lo tanto, entre a y b involucra a los sumo n divisiones como queríamos demostrar.

Proposición: Sean a ≤ b números naturales. El número de divisiones necesarias para calcular el máximo común divisor entre a y b por medio del Algoritmo de Euclides está acotado por 5(D + 1), donde D es la cantidad de cifras del desarrollo decimal de a.

Demostración: Usando el Lema anterior, si queremos estimar el número de divisiones necesarias, deberíamos encontrar todos los n tales que f_{n} ≤ a. Usando la fórmula general de los números de Fibonacci tenemos que:

\frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n} ≤ a

y esto implica

\frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − 1 < a

con lo cual

n log_{10} (\frac{1 + \sqrt{5}}{2}) < log_{10}(\sqrt{5}.(a + 1)) < log_{10}(a) + 1

y por lo tanto

n < 5(log_{10} a + 1)

Notar que log_{10} a es la cantidad de cifras del desarrollo decimal de a.

4.2. El caso de las raíces múltiples:

El razonamiento anterior evidentemente no funciona en el caso en que el polinomio tenga raíces múltiples ya que la matriz no es diagonalizable pero igualmente se puede tratar de encontrar una expresión para los coeficientes de la matriz (C_{P})^{n−1}. Para eso utilizaremos la forma normal de Jordan de dicha matriz. Como la matriz C_{P} es la compañera del polinomio P, tanto el polinomio característico como el minimal de C_{P} es P y por lo tanto, si λ_{1},…, λ_{r} son las raíces distintas de P, la forma normal de Jordan de C_{P} tendrá un solo bloque de Jordan asociado a cada autovalor de P. Es decir, existe una matriz D ∈ C^{k×k} inversible tal que:

D.C_{P} .D^{−1} = ( \begin{matrix}J_{λ_{1}} & 0 & 0 & … & 0 \\ 0 & J_{λ_{2}} & 0 & … & 0 \\ 0 & 0 & J_{λ_{3}} & … & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & J_{λ_{r}} \end{matrix} )

donde cada J_{λ_{i}} es bloque de Jordan, es decir, una matriz del tipo

J_{λ_{i}} = ( \begin{matrix}λ_{i} & 0 & 0 & … & 0 & 0 \\ 1 & λ_{i} & 0 & … & 0 & 0 \\ 0 & 1 & λ_{i} & … & 0 & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & 1 & λ_{i} \end{matrix} )

Elevando la matriz de Jordan de C_{P} a la n − 1 multiplicando por bloques se tiene que:

(C_{P})^{n−1} = D^{−1}. ( \begin{matrix}(J_{λ_{1}})^{n−1} & 0 & 0 & … & 0 \\ 0 & (J_{λ_{2}})^{n−1} & 0 & … & 0 \\ 0 & 0 & (J_{λ_{3}})^{n−1} & … & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & (J_{λ_{r}})^{n−1} \end{matrix} ) .D

Por lo tanto bastará saber elevar un bloque de Jordan para obtener información sobre los coeficientes de (C_{P})^{n−1}. Supongamos que J_{λ_{i}} ∈ C^{j×j} y observemos algunas propiedades: •) El bloque de Jordan J_{λ_{i}} se puede escribir como suma de dos matrices que conmutan:

J_{λ_{i}} = ( \begin{matrix}λ_{i} & 0 & 0 & … & 0 & 0 \\ 0 & λ_{i} & 0 & … & 0 & 0 \\ 0 & 0 & λ_{i} & … & 0 & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & 0 & λ_{i} \end{matrix} ) + ( \begin{matrix}0 & 0 & 0 & … & 0 & 0 \\ 1 & 0 & 0 & … & 0 & 0 \\ 0 & 1 & 0 & … & 0 & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & 1 & 0 \end{matrix} )

Como las dos matrices conmutan, para elevar la suma a la n − 1, podemos usar la fórmula del binomio de Newton.

• •) Si llamamos N a la matriz

N = ( \begin{matrix}0 & 0 & 0 & … & 0 & 0 & 0 \\ 1 & 0 & 0 & … & 0 & 0 & 0 \\ 0 & 1 & 0 & … & 0 & 0 & 0 \\ 0 & 0 & 1 & … & 0 & 0 & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & … & 0 & 1 & 0 \end{matrix} )

y notamos con I_{r} a la matriz identidad en C^{r×r}, tenemos que

N^{1} = ( \begin{matrix}0 & 0 \\ I_{j−1} & 0 \end{matrix} ) ,

N^{2} = ( \begin{matrix}0 0 0 0 & 0 0 0 0 \\ I_{j−2} & 0 0 0 0 \end{matrix} )

y, para 1 ≤ i ≤ j − 1,

N^{i} = ( \begin{matrix}0 … 0 . . . . . . . . . 0 … 0 & 0 … 0 . . . . . . . . . 0 … 0 \\ I_{j−i} & 0 … 0 . . . . . . . . . 0 … 0 \end{matrix} ) .

(es decir, a medida que se eleva la matriz N, los unos van “bajando” una fila por vez).

Si i ≥ j, N^{i} = 0. Así que, si aplicamos la fórmula del binomio de Newton para hallar (J_{λ_{i}})^{n−1}, y con la convención de que \binom{n−1}{i} = 0 si i > n − 1, se tiene:

(J_{λ_{i}})^{n−1} = ( \begin{matrix}λ_{i}^{n−1} & 0 & 0 & … & 0 & 0 \\ \binom{n−1}{1}λ_{i}^{n−2} & λ_{i}^{n−1} & 0 & … & 0 & 0 \\ \binom{n−1}{2}λ_{i}^{n−3} & \binom{n−1}{1}λ_{i}^{n−2} & λ_{i}^{n−1} & … & 0 & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ \binom{n−1}{j−1}λ_{i}^{n−j} & \binom{n−1}{j−2}λ_{i}^{n−j+1} & \binom{n−1}{j−3}λ_{i}^{n−j+2} & … & \binom{n−1}{1}λ_{i}^{n−2} & λ_{i}^{n−1} \end{matrix} )

Luego, tenemos una fórmula para (C_{P})^{n−1}. \binom{n−1}{j−1} es un polinomio de grado j − 1 en n y, si λ_{i} ≠ 0, λ_{i}^{n−j} = λ_{i}^{n−1}.λ_{i}^{1−j}. Por lo tanto, \binom{n−1}{j−1}.λ_{i}^{n−j} = \binom{n−1}{j−1}.λ_{i}^{1−j}.λ_{i}^{n−1} es un polinomio de grado j − 1 en n multiplicado por λ_{i}^{n−1}. Para el caso λ_{i} = 0 usamos la convención 0^{0} = 1 y 0^{j} = 0 si j ∈ ZZ − {0} para resumir la escritura. Queda demostrado entonces el siguiente

Teorema. Sea {x_{n}}_{n∈IN} una sucesión recursiva lineal que satisface un polinomio P ∈ C [X] cuyas raíces complejas no nulas son λ_{1}, λ_{2},…, λ_{r} con multiplicidades s_{1}, s_{2},…, s_{r} respectivamente y 0 es raíz de P con multiplicidad s (eventualmente s = 0). Entonces existen polinomios f_{1}, f_{2},…, f_{r} en C[X] con gr(f_{i}) ≤ s_{i} − 1 o f_{i} = 0 y números complejos c_{1},…, c_{s} tales que

x_{n} = f_{1}(n).λ_{1}^{n−1} + f_{2}(n).λ_{2}^{n−1} + … + f_{r}(n).λ_{r}^{n−1} + ∑_{i=1}^{s} c_{i}.0^{n−i} ∀n ∈ IN.

Encontremos ahora una fórmula general para la sucesión definida en el Ejemplo 6. Recordemos que

\{ \begin{matrix}x_{1} = 0 \\ x_{2} = 3 \\ x_{3} = 13 \\ x_{4} = 34 \\ x_{n+4} = 4x_{n+3} − 6x_{n+2} + 4x_{n+1} − 1x_{n}  ∀ n ∈ IN. \end{matrix}

El polinomio P asociado a esta recursión es

P = X^{4} − 4X^{3} + 6X^{2} − 4X + 1 = (X − 1)^{4}.

Utilizando el teorema anterior para la sucesión {x_{n}}_{n∈IN}, obtenemos que su término general debe ser de la forma

x_{n} = a.n^{3} + b.n^{2} + c.n + d ∀n ∈ IN

para a, b, c y d complejos. Resolviendo el sistema lineal que se obtiene variando n entre 1 y 4, o sea

\{ \begin{matrix}a + b + c + d = 0 \\ 8a + 4b + 2c + d = 3 \\ 27a + 9b + 3c + d = 13 \\ 64a + 16b + 4c + d = 34 \end{matrix}

obtenemos que

x_{n} = \frac{2}{3}n^{3} − \frac{1}{2}n^{2} − \frac{1}{6}n ∀ n ∈ IN.

Ejercicios

Ejercicio 6. Calcular la cantidad de cifras decimales de f_{1000} (el término número 1000 de la sucesión de Fibonacci). Dato: log_{10}(\frac{1+\sqrt{5}}{2}) ≅ 0, 2089876.

Ejercicio 7. Calcular las fórmulas generales de las siguientes sucesiones:

i)  \{ \begin{matrix}a_{1} = 1 , a_{2} = 0 , a_{3} = 1 , a_{4} = 0 \\ a_{n+4} = 10a_{n+3} − 35a_{n+2} + 50a_{n+1} − 24a_{n} & si n ≥ 1 \end{matrix}

ii)  \{ \begin{matrix}a_{1} = 1 , a_{2} = 1 , a_{3} = 1 , a_{4} = 1 \\ a_{n+4} = −6a_{n+3} − 13a_{n+2} − 12a_{n+1} − 4a_{n} & si n ≥ 1 \end{matrix}

iii) a_{n} = ∑_{i=1}^{n} i^{2} si n ≥ 1

iv) a_{n} = ∑_{i=1}^{n} i^{3} si n ≥ 1

v) a_{n} = ∑_{i=1}^{n} i^{4} si n ≥ 1

Ejercicio 8. Sean a , b ∈ C y sea A ∈ C ^{n×n} la matriz

A = ( \begin{matrix}b & a & 0 & 0 & ⋯ & 0 & 0 \\ a & b & a & 0 & ⋯ & 0 & 0 \\ 0 & a & b & a & ⋯ & 0 & 0 \\ 0 & 0 & a & b & ⋯ & 0 & 0 \\ … & … & … & … & … & … & … \\ 0 & 0 & 0 & 0 & ⋯ & b & a \\ 0 & 0 & 0 & 0 & ⋯ & a & b \end{matrix} )

Calcular det(A) en función de los valores de a, b y n.

Ejercicio 9. Dados k ∈ IN_{0} y α ∈ IR, se considera la integral

S_{k} = ∫_{0}^{π} \frac{cos kx − cos kα}{cos x − cos α}dx

i) Probar que S_{k+1} = 2 cos αS_{k} − S_{k−1} ∀k ∈ IN. ii) Calcular S_{k} ∀k ∈ IN_{0}.

Ejercicio 10.

i) Se considera la sucesión definida por la fórmula

a_{n} = (1 + \sqrt{2})^{n} + (1 − \sqrt{2})^{n}

Encontrar una definición por recurrencia lineal para {a_{n}}_{n∈IN}. Deducir que [(1 + \sqrt{2})^{n}] ≡ n + 1 ( mod 2) ∀n ∈ IN (donde [x] significa parte entera de x).

ii) Encontrar p y q números naturales tales que [(\frac{p+\sqrt{q}}{2} )^{n}] ≡ n ( mod 2) ∀n ∈ IN.

Ejercicio 11. Sean A y E vértices opuestos de un octógono regular. Una rana está en el vértice A y comienza a saltar de vértice en vértice, con las siguientes dos reglas:

I) Desde un vértice cualquiera del octógono distinto de E, puede saltar a cualquiera de los dos vértices adyacentes.

II) Cuando llega al vértice E, la rana deja de saltar y se queda allí. Para cada número natural n, sea a_{n} el número de caminos distintos que puede seguir la rana con exactamente n saltos, terminando en E. Probar que: a_{2n−1} = 0 y a_{2n} = \frac{1}{\sqrt{2}}((2 + \sqrt{2})^{n−1} − (2 − \sqrt{2})^{n−1}) ∀ n ∈ IN.

5. Caracterización

Hasta ahora hemos probado que, si {x_{n}}_{n∈IN} es una sucesión recursiva lineal, existen f_{1}, f_{2},…, f_{r} en C[X], s ∈ IN_{0} y λ_{1},…, λ_{r}, c_{1},…, c_{s} números complejos tales que

x_{n} = f_{1}(n).λ_{1}^{n−1} + f_{2}(n).λ_{2}^{n−1} + … + f_{r}(n).λ_{r}^{n−1} + ∑_{i=1}^{s} c_{i}.0^{n−i} ∀n ∈ IN.

Ahora, utilizando algunos resultados previos y un lema técnico, vamos a demostrar que todas las sucesiones de esta forma son recursivas lineales.

Lema. Sean n y r ∈ IN ∪ {0} . Entonces

∑_{i=0}^{r+1} \binom{r + 1}{i}(−1)^{r+1−i}(n + i)^{r} = 0.

Demostración: Sea P el polinomio

P = ∑_{i=0}^{r+1} \binom{r + 1}{i}(−1)^{r+1−i}(X + i)^{r}.

P (n) = 0 ∀n ∈ IN ∪ {0} si y sólo si P = 0. Calculando los coeficientes de grado j de P (0 ≤ j ≤ r), basta mostrar que

∑_{i=0}^{r+1} \binom{r + 1}{i}(−1)^{r+1−i}i^{h} = 0

para todo r ∈ IN ∪ {0} y 0 ≤ h ≤ r (donde h = r − j). Vamos a probarlo por inducción.

El caso r ∈ IN ∪ {0} y h = 0 sale aplicando la fórmula del binomio de Newton a (1 − 1)^{r+1} (recordemos que 0^{0} es por convención 1).

Supongamos ahora que el resultado es cierto para un número r ∈ IN ∪ {0} y h = 0, 1,…, r. Vamos a probar la igualdad para r + 1 y h = 0, 1,…, r + 1.

La igualdad vale si h = 0. Cuando 1 ≤ h ≤ r + 1 consideramos k = h − 1. Entonces 0 ≤ k ≤ r y

∑_{i=0}^{r+2} \binom{r + 2}{i}(−1)^{r+2−i} i^{h} = ∑_{i=1}^{r+2} \binom{r + 2}{i}(−1)^{r+2−i} i^{k+1} =

= ∑_{i=1}^{r+2}(−1)^{r+2−i}\binom{r + 1}{i − 1}\frac{r + 2}{i} i^{k+1} = (r + 2) ∑_{i=1}^{r+2}(−1)^{r+2−i}\binom{r + 1}{i − 1} i^{k} =

= (r+2) ∑_{i=0}^{r+1}(−1)^{r+1−i}\binom{r + 1}{i} (i+1)^{k} = (r+2) ∑_{i=0}^{r+1}(−1)^{r+1−i}\binom{r + 1}{i} (∑_{j=0}^{k} \binom{k}{j}(i)^{j}) =

= (r + 2) ∑_{j=0}^{k} \binom{k}{j} (∑_{i=0}^{r+1}(−1)^{r+1−i}\binom{r + 1}{i} (i)^{j}) = (r + 2) ∑_{j=0}^{k} \binom{k}{j}0 = 0.

Ahora podemos probar el siguiente

Teorema. Sean f_{1}, f_{2},…, f_{r} en C[X], s ∈ IN_{0} y λ_{1},…, λ_{r}, c_{1},…, c_{s} números complejos. Entonces la sucesión definida por

x_{n} = f_{1}(n).λ_{1}^{n−1} + f_{2}(n).λ_{2}^{n−1} + … + f_{s}(n).λ_{s}^{n−1} + ∑_{i=1}^{s} c_{i}.0^{n−i} ∀n ∈ IN

es recursiva lineal.

Demostración: Como S es un subespacio vectorial de C^{IN}, basta mostrar que, dado un número complejo λ y r ∈ IN ∪ {0}, la sucesión {n^{r}.λ^{n−1}}_{n∈IN} es recursiva lineal (las sucesiones del tipo 0^{n−i} son evidentemente recursivas lineales). Para probarlo, tenemos que encontrar un polinomio P ∈ C[X] tal que {n^{r}.λ^{n−1}}_{n∈IN} satisfaga P. Si analizamos la demostración del Teorema anterior, vemos que λ tiene que ser raíz de P con multiplicidad por lo menos r + 1. Consideremos

P = (X − λ)^{r+1} = ∑_{i=0}^{r+1} \binom{r + 1}{i}(−λ)^{r+1−i}X^{i}

y veamos si {n^{r}.λ^{n−1}}_{n∈IN} la satisface:

∑_{i=0}^{r+1} \binom{r + 1}{i}(−λ)^{r+1−i} (n + i)^{r} λ^{n+i−1} = λ^{n+r} ∑_{i=0}^{r+1} \binom{r + 1}{i}(−1)^{r+1−i} (n + i)^{r} = 0

usando el Lema anterior.

Por lo tanto {n^{r}.λ^{n−1}}_{n∈IN} satisface P y es recursiva lineal como queríamos demostrar.

Ejercicio Ejercicio 12. Probar que el conjunto S es un subanillo de C^{IN} con el producto definido coordenada a coordenada.

6. Una generalización: Sucesiones mutuamente recursivas lineales

Consideremos ahora las sucesiones {a_{n}}_{n∈IN} y {b_{n}}_{n∈IN} definidas por

\{ \begin{matrix}a_{1} = 1 a_{2} = 0 b_{1} = 0 b_{2} = 1 \\ a_{n+2} = 2b_{n+1} + a_{n} b_{n+2} = a_{n+1} + b_{n}. \end{matrix}

Tratemos de traducir las ideas precedentes a esta situación:

( \begin{matrix}0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix} )^{n−1} . ( \begin{matrix}a_{1} \\ a_{2} \\ b_{1} \\ b_{2} \end{matrix} ) = ( \begin{matrix}a_{n} \\ a_{n+1} \\ b_{n} \\ b_{n+1} \end{matrix} ) .

El polinomio característico de la matriz es

X = X^{4} − 4X^{2} + 1

y todas sus raíces son simples, por lo tanto la matriz es diagonalizable. Luego existen complejos α_{1}, α_{2}, β_{1}, β_{2}, γ_{1}, γ_{2}, δ_{1} y δ_{2} tales que a_{n} = α_{1}.(\sqrt{2 + \sqrt{3}})^{n−1} + β_{1}.(−\sqrt{2 + \sqrt{3}})^{n−1} + γ_{1}.(\sqrt{2 − \sqrt{3}})^{n−1} + δ_{1}.(−\sqrt{2 − \sqrt{3}})^{n−1} y que b_{n} = α_{2}.(\sqrt{2 + \sqrt{3}})^{n−1} + β_{2}.(−\sqrt{2 + \sqrt{3}})^{n−1} + γ_{2}.(\sqrt{2 − \sqrt{3}})^{n−1} + δ_{2}.(−\sqrt{2 − \sqrt{3}})^{n−1}.

Resolviendo los sistemas lineales asociados a los primeros cuatro términos de las sucesiones tenemos que, ∀n ∈ IN, a_{n} = (\frac{3+\sqrt{3}}{12}) .(1 + (−1)^{n−1}). (\sqrt{2 + \sqrt{3}})^{n−1} + (\frac{3−\sqrt{3}}{12}) .(1 + (−1)^{n−1}). (\sqrt{2 − \sqrt{3}})^{n−1} y

b_{n} = (\frac{\sqrt{3}}{12}) .(1 + (−1)^{n}). (\sqrt{2 + \sqrt{3}})^{n} + (\frac{−\sqrt{3}}{12}) .(1 + (−1)^{n}). (\sqrt{2 − \sqrt{3}})^{n}.

Este método se puede adaptar a varias sucesiones mutuamente recursivas lineales. Como la demostración es esencialmente la misma que en el caso de una sola sucesión, nos limitaremos a dar una definición y a establecer el resultado.

Definición: Sean {a_{n}^{(i)}}_{n∈IN} (1 ≤ i ≤ r) sucesiones en C^{IN}. Se dice que son mutuamente recursivas lineales si existe k ∈ IN y complejos α_{j}^{(i)} (1 ≤ i ≤ r , 0 ≤ j ≤ k − 1) tales que

a_{n+k}^{(i)} = ∑_{1≤s≤r} ( ∑_{0≤j≤k−1} α_{j}^{(s)}.a_{n+j}^{(s)})  (1 ≤ i ≤ r)  ∀n ∈ IN.

Es decir, cada término de cada sucesión depende linealmente de los k términos anteriores de todas las sucesiones. En este caso podemos obtener una matriz A en C^{rk×rk} tal que

A^{n−1}. ( a_{1}^{(1)} ; ⋮ ; a_{k}^{(1)} ; ⋮ ; a_{1}^{(r)} ; ⋮ ; a_{k}^{(r)} ) = ( a_{n}^{(1)} ; ⋮ ; a_{n+k−1}^{(1)} ; ⋮ ; a_{n}^{(r)} ; ⋮ ; a_{n+k−1}^{(r)} )

Usando la forma normal de Jordan de A para obtener A^{n−1} como antes, podemos dar una fórmula del término general de cada sucesión {a_{n}^{(i)}}_{n∈IN}. (La única diferencia es que, como la matriz A no es una matriz compañera, su forma de Jordan puede tener más de un bloque de Jordan para cada autovalor, pero los cálculos son esencialmente los mismos).

Para terminar, podemos enunciar el siguiente resultado.

Proposición : Sean {a_{n}^{(i)}}_{n∈IN} (1 ≤ i ≤ r) sucesiones mutuamente recursivas lineales en C^{IN}. Entonces, cada {a_{n}^{(i)}}_{n∈IN} (1 ≤ i ≤ r) es una sucesión recursiva lineal y por lo tanto satisface una fórmula como la de los Teoremas anteriores.

Ejercicios

Ejercicio 13. Calcular una fórmula general para la sucesión {a_{n}}_{n∈IN} definida por

\{ \begin{matrix}a_{1} = 1  a_{2} = 1 \\ a_{n+2} = a_{n+1} + 2a_{n} + (−1)^{n} \end{matrix}

Ejercicio 14. Sea {f_{n}}_{n∈IN} la sucesión de Fibonacci. Calcular el término general de la sucesión {F_{n}}_{n∈IN} definida por

\{ \begin{matrix}F_{1} = 1  F_{2} = 1 \\ F_{n+2} = F_{n+1} + F_{n} + f_{n+2}  ∀ n ∈ IN \end{matrix}

Ejercicio 15. Calcular una fórmula general para las sucesiones {a_{n}}_{n∈IN} y {b_{n}}_{n∈IN} definidas por

\{ \begin{matrix}a_{1} = 1  a_{2} = 0  b_{1} = 1  b_{2} = 1 \\ a_{n+2} = 4a_{n+1} + 2b_{n}  b_{n+2} = 8a_{n} + 4b_{n+1} \end{matrix}

Referencias

[1] R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics - A Foundation for Computer Science, Addison-Wesley Publishing Company, 1992.

[2] K. Hoffman and R. Kunze, Algebra Lineal, Prentice Hall Hispanoamericana, 1973.

[3] A. Markushévich, Sucesiones Recurrentes, Editorial MIR, 1974.

[4] M. Spiegel, Finite Differences and Difference Equations, McGraw-Hill Publishing Company, 1989.

El enunciado del ejemplo de sucesiones mutuamente recursivas resuelto en 6 fue extraído de [1], donde también se resuelven sucesiones recursivas pero usando funciones generatrices (series formales de potencias). También se extrajeron de allí los ejercicios 10, 13 y 14. Los ejercicios 8 y 9 fueron extraídos de [4] donde además se pueden encontrar muchas otras aplicaciones de este tema (a la física, a la probabilidad, etc.). El ejercicio 11 fue extraído de la Competencia E. Paenza del año 1990. En [3] se trata el tema de las sucesiones recursivas lineales con un nivel elemental pero casi sin demostraciones. Finalmente, las nociones básicas de Algebra Lineal, forma normal de Jordan y matrices compañeras se pueden encontrar en [2].