Download Elementos Matematica Discreta PDF

TitleElementos Matematica Discreta
TagsDivision (Mathematics) Real Number Prime Number Numbers Equations
File Size3.2 MB
Total Pages180
Document Text Contents
Page 90

80 CAPÍTULO 4. SUCESIONES RECURRENTES LINEALES

Definición 4.2.- Las recurrencias lineales se clasifican en homogéneas y no homogéneas, según sea el término
independiente f(n). Así, si en la ecuación (4.6) f(n) = 0, es decir, f(n) es la función constante igual a cero,
diremos que la recurrencia es homogénea. En caso contrario, diremos que la recurrencia es no homogénea.

En muchas ocasiones una recurrencia no homogénea puede transformarse en otra que sí lo es. Por ejemplo,
la recurrencia dada para el problema de las Torres de Hanoi (ejemplo 4.1), Tn = 2Tn−1 + 1, es una recurencia
de orden uno no homogénea. Sin embargo, escribamos la recurrencia para n + 1 y restemos las expresiones
correspondientes a Tn+1 y Tn

Tn+1 = 2Tn + 1, Tn = 2Tn−1 + 1
Tn+1 − Tn = 2Tn − 2Tn−1
Tn+1 = 3Tn − 2Tn−1.

Observamos que los términos de Tn satisfacen una recurrencia lineal homogénea de orden dos.
Análogamente, la recurrencia para el caso de las regiones en que queda dividido el plano por n rectas

(ejemplo 4.2) puede transformarse en otra homogénea por un procedimiento similar. En este caso en la
recurrencia no homogénea Rn = Rn−1 + n, consideramos los términos Rn y Rn+1. Restándolos se obtiene

Rn+1 −Rn = Rn −Rn−1 + 1,

es decir
Rn+1 = 2Rn −Rn−1 + 1.

Considerando ahora Rn+2 y volviendo a restar se obtiene finalmente

Rn+2 = 3Rn+1 − 3Rn +Rn−1,

que es una recurrencia lineal homogénea de orden 3.
Como se ve, el precio que hay que pagar para convertir una recurrencia no homogénea en otra homogénea

es el aumento en el orden de la misma. Sin embargo, para la resolución de las recurrencias homogéneas existe
un método general que consideraremos a continuación.

4.3. Resolución de recurrencias lineales homogéneas
Empecemos resolviendo una recurrencia lineal de primer orden homogénea. Esto es, una recurrencia dada

por la ecuación
an+1 = qan, n ≥ 1. (4.7)

Observemos que cualquier progresión geométrica de razón q cumple esta ecuación. De hecho, aplicando
sucesivamente la relación (4.7) se obtiene

an+1 = a1qn, n ≥ 0. (4.8)

En este caso, la sucesión queda determinada de manera única por el primer término de la misma y por el
coeficiente q. Una fórmula explícita para los términos de la sucesión está dada por (4.8).

Consideremos ahora el caso de una recurrencia lineal homogénea de orden k dada por la relación

an+k = c1an+k−1 + c2an+k−2 + · · ·+ ckan, n ≥ 1. (4.9)

Esta ecuación es satisfecha por infinitas sucesiones, al igual que la ecuación (4.7) era satisfecha por cualquier
progresión geométrica de razón q. En este caso la sucesión quedará determinada de manera única una vez
que se conozcan los k primeros términos de la misma.

Por ejemplo, no es complicado comprobar que las sucesiones de la forma an = A + B2n, con A y B dos
números reales cualesquiera, satisfacen la recurrencia an+1 = 3an − 2an−1, n ≥ 1. Ahora bien, si fijamos los
dos primeros términos de la sucesión (an), ésta queda determinada de forma única. En efecto, si a0 = a1 = 1
entonces an = 1 para todo n ≥ 0. Sin embargo, si a0 = 1/2 y a1 = 1 entonces an = 2n−1 para todo n ≥ 0.
En general, dados los dos primeros términos a0 y a1, los coeficientes A y B son la única solución del sistema
de ecuaciones {

A + B = a0
A + 2B = a1.

Page 91

4.3. RECURRENCIAS HOMOGÉNEAS 81

Con el fin de encontrar una fórmula para dar el término general de una recurrencia lineal, veamos primero
algunas propiedades de las soluciones de la ecuación (4.9).

Teorema 4.1 Si (xn) e (yn) son dos sucesiones que satisfacen la ecuación (4.9), entonces la sucesión (zn),
tal que zn = Axn +Byn, con A,B ∈ R, también satisface (4.9).

Demostración. Por ser (xn) e (yn) sucesiones que verifican (4.9) se tiene{
xn+k = c1xn+k−1 + c2xn+k−2 + · · ·+ ckxn,
yn+k = c1yn+k−1 + c2yn+k−2 + · · ·+ ckyn.

Multiplicando la primera ecuación por A, la segunda por B y sumando, resulta

Axn+k +Byn+k = c1(Axn+k−1 +Byn+k−1) + c2(Axn+k−2 +Byn+k−2)

+ · · ·+ ck(Axn +Byn).

Es decir, la sucesión (zn) dada por zn = Axn +Byn, también satisface la ecuación (4.9).

Este resultado nos dice que cualquier combinación lineal de sucesiones que satisfacen (4.9) también sa-
tisface (4.9). A partir de aquí, no es difícil probar que cualquier sucesión que satisface (4.9) se puede poner
como combinación lineal de una base de k sucesiones independientes que también satisfacen (4.9). En efecto,
sean (xmn ), con m = 1, . . . , k, las k sucesiones independientes. Entonces la sucesión (an) cuyos k primeros
términos son a1, a2, . . ., ak se podrá obtener como combinación lineal de (xmn ) siempre que el sistema de
ecuaciones 



A1x
1
1 +A2x21 + · · ·+Akxk1 = a1,

A1x
1
2 +A2x22 + · · ·+Akxk2 = a2,

...
A1x

1
k +A2x

2
k + · · ·+Akx

k
k = ak,

tenga solución única. En este caso tiene que ser∣∣∣∣∣∣∣∣∣∣∣

x11 x
2
1 · · · xk1

x12 x
2
2 · · · xk2

...
...

...
...

x1k x
2
k · · · x

k
k

∣∣∣∣∣∣∣∣∣∣∣
6= 0,

que es la condición de independencia de las sucesiones (xmn ).
Por lo tanto, el problema de encontrar la sucesión que satisface (4.9) y cuyos k primeros términos son a1,

a2, . . ., ak pasa por encontrar k sucesiones independientes que cumplan (4.9).
A la vista de que una recurrencia de orden uno es satisfecha por progresiones geométricas, podemos buscar

si existen progresiones geométricas
an = λn, (4.10)

que satisfacen (4.9). En este caso se tiene que cumplir

λn+k = c1 λn+k−1 + c2 λn+k−2 + · · ·+ ck λn.

Dividiendo por λn, obtenemos una ecuación polinómica de orden k:

λk − c1λk−1 − c2λk−2 − · · · − ck = 0. (4.11)

Definición 4.3.- La ecuación polinómica anterior (4.11) recibe el nombre de ecuación característica asociada
a la ecuación recurrente homogénea (4.9).

Similer Documents