7/29/2019 Ecuaciones de Recurrencia[1]

1/3

Apendice A

Ecuaciones de recurrencia

A.1. Primer orden

Definicion A.1.1. Una ecuacion de recurrencia de primer orden es una expresion de la formaan = f(an1).

La ecuacion de recurrencia origina una sucesion de numeros donde cada uno de ellos depende dealguna forma solo del numero anterior. Por ejemplo, consideremos los numeros 2, 5, 11, 23, 47, 95,...los cuales cumplen la relacion an = 2an1 + 1 pues 5 = 2(2) + 1, 11 = 2(5) + 1, 23 = 2(11) + 1 yas sucesivamente con todos.

Si tenemos una relacion de recurrencia de primer orden podemos construir toda la sucesion denumeros a partir de un numero inicial. Por ejemplo, en la sucesion anterior si solo sabemos quean = 2an1 + 1 no podemos construir la sucesion pues necesitamos saber el numero inicial. Por lotanto, si el numero inicial es a0 = 2, entonces tendramos que a1 = 2(2)+ 1 = 5, a2 = 2(5)+ 1 = 11,a3 = 2(11) + 1 = 23 y as sucesivamente; sin embargo, dependemos del numero anterior para conocerel siguiente lo que hara complicado encontrar por ejemplo a15.

La siguiente proposicion nos proporciona una formula para encontrar a15 sin conocer los numerosanteriores salvo el inicial.

Proposicion A.1.2. Sea an una ecuacion de recurrencia de primer orden que tiene la forma an =kan1 + d con k, d R y supongamos que el numero inicial es a0. Entonces

an =

kna0 +kn 1

k 1d k = 1

a0 + nd k = 1(A.1)

Demostracion: Notemos que

a1 = ka0 + da2 = ka1 + d = k(ka0 + d) + d = k2a0 + (k + 1)da3 = ka2 + d = k(k

2a0 + (k + 1)d) + d = k3a0 + (k

2 + k + 1)d

y as sucesivamente obtenemos que

an = kna0 + (k

n1 + kn3 + + k + 1)d

Dividamos la prueba por casos:

1. k = 1. Como kn1 + kn2 + + k + 1 =kn 1

k 1por ser una serie geometrica, concluimos que

an = k

na0 +kn 1

k 1d.

99

7/29/2019 Ecuaciones de Recurrencia[1]

2/3

100 APENDICE A. ECUACIONES DE RECURRENCIA

2. k = 1. Es facil ver que kn1+kn2+ +k+1 = 1 + 1 + + 1 nveces

= n. Por lo tanto an = a0+nd.

Ejemplo A.1.3. Supongamos que an = 2an1 + 1 y que a0 = 2, determina a15.

Demostracion: Por la proposicion A.1.2 tenemos que

a15 = kna0 +

kn 1

k 1d = 215(2) +

215 1

2 12 = 131070.

A.2. Segundo orden

Definicion A.2.1. Una ecuacion de recurrencia de segundo orden es una expresion de la forma

an = f(an1, an2).

En las ecuaciones de recurrencia de segundo orden, para poder calcular el termino an es necesarioconocer los dos terminos anteriores, esta es la razon por la que es de segundo orden. En estos casosnecesitaremos tener dos valores iniciales que denotaremos por a0 y a1.

Al igual como lo hicimos en el caso de las ecuaciones de recurrencia de primer orden, vamos a en-contrar una formula que nos ayude a encontrar explcitamente an cuando es de la forma can1+dan1sin necesidad de tener que encontrar todos los terminos de la sucesion sino solamente conociendo losdos primeros. El procedimiento lo iremos describiendo a traves de dos ejemplos.

Caso 1: Races diferentes

Consideremos la ecuacion de recurrencia de segundo orden an = 3an1+4an2 con a0 = 1, a1 = 1.Enlistemos el procedimiento a seguir:

1. Cambiar an por xn en la ecuacion de recurrencia quedando de esta manera la nueva ecuacion

xn = 3xn1 + 4xn2.

2. Dividir entre xn2 para obtener una ecuacon de segundo grado, siendo esta x2 = 3x + 4.

3. Encontrar las soluciones de la ecuacion anterior siendo estas x = 4 y x = 1. Como comentario,las races deben ser diferentes como sucedio en este caso.

4. La expresion de an esta dada por an = c(4)n+ d(1)n. Notar que an es una combinacion lineal

de las soluciones encontradas en el paso anterior y c y d son constantes que se determinan enel siguiente paso.

5. Hallar las constantes c y d sustituyendo en la expresion de an los valores iniciales a0 y a1.De esta manera obtenemos el sistema de ecuaciones a0 = c + d = 1 y a1 = 4c d = 1 cuyas

soluciones son c =2

5y d =

3

5.

6. Sustituir los valores de c y d en la expresion de an, siendo esta finalmente

an =2

5(4)n +

3

5(1)n.

7/29/2019 Ecuaciones de Recurrencia[1]

3/3

A.2. SEGUNDO ORDEN 101

Caso 2: Races iguales

En este caso los pasos a seguir son exactamente los mismos que en el caso uno, lo unico quesera diferente es la forma de la expresion de an. Consideremos la ecuacion de recurrencia an =4an1 4an2 con a0 = 1 y a1 = 1. Haciendo el cambio de variable obtenemos x

n = 4xn1 4xn2

que al dividir entre xn2 da origen a la ecuacion x2

4x + 4 = 0 cuyas soluciones son x = 2 y x = 2.En este momento nos damos cuenta de que estamos en el segundo caso y no en el primero pues lasraces son iguales.

La expresion de an sera an = c(2)n + dn(2)n. Notar que la diferencia con respecto al caso uno,

es la n que multiplica a la d. Seguidamente hallamos los valores de c y d sustituyendo los valoresiniciales a0 = 1 y a1 = 1 en la expresion de an, lo que nos proporciona las ecuaciones a0 = c = 1 y

a1 = 2c + 2d = 1 cuyas soluciones son c = 1 y d = 1

2. Por lo tanto, la expresion final para an es

an = 2n

1

2n(2)n = 2n n2n1.