DiscII 3
DiscII 3
DiscII 3
Capitulo III
Relaciones de recurrencia
Relaciones de Recurrencia
Definición 1
Una relación de recurrencia para la secuencia {an} es una ecuación que expresa an en términos de uno o
mas de los términos previos de la secuencia (a0, a1, ....., an-1), para todos los enteros n con n≥n0, donde
n0 es un entero no negativo. Una secuencia es llamada una solución de una relación de recurrencia si
sus términos satisfacen la relación de recurrencia.
Ejemplo1: Sea {an} una secuencia que satisface la relación de recurrencia an= an-1-an-2 para n=2, 3, 4,
... y suponga que a0=3 y a1=5. determinar a2 y a3.
R// a2=2 y a3=-3
Ejemplo2: Determine si la secuencia {an} es una solución de la relación de recurrencia an= 2an-1-an-2
para n=2, 3, 4 ....., donde an= 3n para cada entero n no negativo.
R// suponga que an= 3n para cada entero n no negativo. Entonces para n≥2 vemos que:
2an-1-an-2 = 2(3(n-1)) –(3(n-2)) = 6n-6-3n+6 = 3n = an , por lo tanto, {an}, donde an= 3n, es una
solución de la relación de recurrencia.
Ejemplo3: Determine si la secuencia {an} es una solución de la relación de recurrencia an= 2an-1-an-2
para n=2, 3, 4 ....., donde an= 2n para cada entero n no negativo.
R// suponga que an= 2n para cada entero n no negativo. Entonces para n≥2 vemos que:
2an-1-an-2 = 2(2n-1) –(2n-2) = 2(21)–(20) = 3 ≠ an = 4, por lo tanto, {an}, donde an= 2n, no es una
solución de la relación de recurrencia.
Ejemplo4: Cuales de las siguientes secuencias {an} son soluciones de la relación de recurrencia
an=8an-1-16an-2 ?
an= 0 (No) an= 2n (No) an= 4n (Si) an= n4n (Si)
Las condiciones iniciales para una secuencia especifican los términos que preceden al primer termino
donde la relación de recurrencia se hace efectiva. Una relación de recurrencia junto con las condiciones
iniciales proporcionan una definición recursiva de la secuencia.
Las relaciones de recurrencia pueden ser usadas para contar cadenas de bits de una longitud
especificada que tiene cierta propiedad
Ejemplo6:
Encuentre una relación de recurrencia y de valores de condición inicial para el numero de cadenas de n
bits que no tienen 2 consecutivos 0s. Cuantas son de longitud 5 ?.
R// Sea an quien denota el numero de cadenas de longitud n que no tienen 2 0’s consecutivos. Por la
regla, este numero es igual a la suma de:
• Cadenas de longitud n-1 sin ceros consecutivos con un 1 adicionado al final. Que corresponde a an-1
• Cadenas de longitud n-1 sin ceros consecutivos con un 0 adicionado al final. Para que estas no
tengan 2 0s consecutivos deben tener su n-1 bit en 1. Es claro que lo anterior corresponde a cadenas
de longitud de n-2 sin 2 0s consecutivos (a los cuales se les adicionara 10 al final). Que corresponde
a an-2
Luego an = an-1 + an-2 para n≥3. Donde las condiciones iniciales son a1 = 2 y a2 = 3.
Donde:
a5 = a4+a3 =(a3+a2) + (a2+a1) = ((a2+a1) + a2) + (a2+a1)
= (3+2+3)+(3+2) = 13
Note que { an } satisface la misma relación de recurrencia que fibonaci, pero las condiciones iniciales
están desplazadas (a1= f3 y a2= f4) de ahí que an= fn+2.
Puestas que las mencionadas anteriormente son las únicas alternativas existentes para crear cadenas de
longitud n validas. Tenemos:
an= 9an-1 + 10n-an-1 = 8an-1 + 10n-1.
Ejemplo8:soluciones interactivas
En algunos casos, es posible encontrar soluciones interactivas (ej: para calcular el interés compuesto).
Encontrar soluciones de este tipo, para las siguientes ecuaciones de recurrencia.
an= 3an-1, a0=2 (2.3n) an=an-1+2, a0=3 (2n+3)
an= an-1+n a0=1 (1+n(n+1)/2) an=an-1+2n+3, a0=4 (n2+4n+4)
Nota: la relación de recurrencia en la definición es lineal puesto que el lado derecho es una suma de
múltiplos de los términos previos de la secuencia. Es homogénea puesto que ninguno de los términos
no son múltiplos de los aj. Los coeficientes de los términos son todos constantes (no dependen de n).
El grado es k porque es expresada en términos de los k términos previos de la secuencia.
Ejemplo1:
Defina características de las ecuaciones de recurrencia:
• Pn=(1.11)Pn-1 . Es lineal homogénea de grado 1
• fn= fn-1 + fn-2 . Es lineal homogénea de grado 2
• an= an-5. Es lineal homogénea de grado 5
• an= an-1 + a2n-2 . No es lineal
• Hn= 2Hn-1 + 1. No es homogénea
• Bn= nBn-1. No tiene coeficientes constantes
Consulta:
Solucionar las relaciones de recurrencia siguiente teniendo en cuenta las condiciones iniciales dadas:
an= 2an-1 an=5an-1-6an-2
n
para n≥1, a0=3 (3.2 ) para n≥2, a0=1 a1=0 ?
Teorema1
Sean c1, c2 números reales. Suponga que r2 - c1r - c2 = 0 tienen 2 raíces diferentes r1 y r2. Entonces la
secuencia {an} es una solución de la relación de recurrencia an=c1an-1+c2an-2 si y solo si an= α1r1n+
α2r2n para n=0, 1, 2......, donde α1 y α2 son constantes.
Matemáticas Discretas II
Capitulo III
Relaciones de recurrencia
Ejemplo1:
Cuál es la solución de la ecuación de recurrencia an = an-1 + 2an-2 con a0 = 2 y a1 = 7 ?
R// Es claro que c1=1 y c2 = 2. Luego la ecuación característica es r2 - r - 2 = 0. obteniendo las raíces
características, estas son: r=2 y r=-1. De ahí que la secuencia { an } es una solución a la relación de
recurrencia si y solo si:
an= α12n+ α2(-1)n . para algunas constantes α1 y α2. verificar que α1=3 y α2.= -1. Y que
entonces la solución a la ecuación de recurrencia y condiciones iniciales es la secuencia { an } con an=
3*2n-(-1)n
Ejemplo3:
Cuál es la solución de la ecuación de recurrencia an = 4an-2 con a0 = 0 y a1 = 4 ?
R// an = (2)n-(-2)n
Teorema2.
Sean c1, c2 números reales con c2≠0. Suponga que r2 - c1r - c2 = 0 tienen solamente una raíz r0. Una
secuencia {an} es una solución de la relación de recurrencia an=c1an-1+c2an-2 si y solo si an= α1r0n+
α2nr0n para n=0, 1, 2......, donde α1 y α2 son constantes.
Ejemplo1:
Cual es la solución de la ecuación de recurrencia
an = 6an-1 - 9an-2 con a0 = 1 y a1 = 6 ?
R// Es claro que c1=6 y c2 = -9. Luego la ecuación característica es r2 - 6r + 9 = 0. obteniendo las raíces
características, estas es única y es r=3. De ahí que la secuencia { an } es una solución a la relación de
recurrencia si y solo si:
an= α13n+ α2n3n . para algunas constantes α1 y α2. Verificar que α1=1 y α2=1. Y que entonces
la solución a la ecuación de recurrencia y condiciones iniciales es la secuencia { an } con an= 3n+ n3n
Ejemplo2:
Indicar la solución de la ecuación de recurrencia an=4an-1 - 4an-2 con a0 = 6 y a1 = 8?
R// an = 6(2)n-2n(2)n
Teorema3.
Sean c1, c2,......,ck números reales. Suponga que la ecuación característica rk-c1rk-1- ...-ck = 0 tiene k raíces
distintas r1, r2, ....,rk,. Entonces una secuencia { an } es una solución de la relación de recurrencia
an=c1an-1+c2an-2+ ..... +ckan-k si y solo si
an= α1r1n+α2r2n+...+αkrkn para n=0, 1, 2......
donde α1, α2 , ...., αk son constantes.
Matemáticas Discretas II
Capitulo III
Relaciones de recurrencia
Ejemplo1:
Cuál es la solución de la ecuación de recurrencia an = 6an-1 - 11an-2 + 6an-3 con a0 = 2, a1 = 5 y a2 = 15?
R// Es claro que c1=6, c2=-11, c3=6. Luego la ecuación característica es r3-6r2+11r-6=0. obteniendo las
raíces características, estas son r1=1, r2=2, r3=3 . De ahí que las soluciones a esta relación de
recurrencia sean de la forma:
an= α11n+ α22n+α33n. para algunas constantes α1, α2, α3. Resolviendo simultáneamente esas 3
ecuaciones tenemos que α1=1, α2=-1 y α3=2. Y que entonces la solución a la ecuación de recurrencia y
condiciones iniciales es la secuencia { an } con an=1- 2n+ 2*3n
Ejemplo2:
Indicar las soluciones a las siguientes ecuaciones de recurrencia
•
an=7an-2 + 6an-3 con a0 = 9 , a1 = 10 y a2 = 32? R// an = 8(-1)n - 3(-2)n + 4(3)n
Teorema4.
Sean c1, c2,......,ck números reales. Suponga que la ecuación característica rk-c1rk-1- ...-ck = 0 tiene t raíces
distintas r1, r2, ....,rt con multiplicidades m1, m2, ....,mt, respectivamente, asi que mi≥1 para i=1,2, ...t y
m1+m2+.....+mt=k. Entonces una secuencia { an } es una solución de la relación de recurrencia
an=c1an-1+c2an-2+ .....+ +ckan-k si y solo si
an= (α1,0+α1,1n+...+α1,m1-1nm1-1) r1n +
(α2,0+α2,1n+...+α2,m2-1nm2-1) r2n +
+…..+ (αt,0+αt,1n+...+αt,mt-1nmt-1) rtn
para n=0, 1, 2......, donde αi,j, son constantes para 1≤i≤t y o≤j≤mi-1
Ejemplo1:
Suponga que las raíces de la ecuación características de una relación de recurrencia lineal son 2,2,2,5,5
y 9. Cual es la forma de la solución general?
R// an = (α1,0+α1,1n+α1,2n2) 2n + (α2,0+α2,1n)5n + (α3,0) 9n
Ejemplo2:
Encuentre la solución a la relación de recurrencia an=-3an-1-3an-2-an-3. con a0=1, a1= -2 y a2= -1
R// Es claro que c1=-3, c2=-3, c3= -1. Luego la ecuación característica es r3+3r2+3r+1=0=(r+1)3. Luego
hay solo una raíz r=-1 de multiplicidad 3. De ahí que las soluciones a esta relación de recurrencia son
de la forma:
an=(α1,0 + α1,1n +α1,2n2)(-1)n. para algunas constantes α1,0, α1,1, y α1,2. Resolviendo
simultáneamente esas 3 ecuaciones tenemos que α1,0=1, α1,1=3 y α1,2= -2. De ahí que la solución a la
ecuación de recurrencia y condiciones iniciales es la secuencia {an} con
an=(1 + 3n - 2n2)(-1)n
Matemáticas Discretas II
Capitulo III
Relaciones de recurrencia
Una relación de recurrencia lineal no homogénea con coeficientes constantes, es una relación de la
forma:
an=c1an-1+c2an-2+ …. +ckan-k + F(n). Donde c1, c2,....,ck son números reales y F(n) es una función no
igual a 0 que depende solo de n. la relación de recurrencia:
an=c1an-1+c2an-2+ …. +ckan-k es llamada la relación de recurrencia homogénea asociada.
Teorema5.
Si {an(p)} es una solución particular de la relación de recurrencia no homogénea con coeficientes
constantes:
an=c1an-1+c2an-2+ …. +ckan-k + F(n).
Entonces cada solución es de la forma {an(p)+ an(h)}, donde {an(h)} es una solución de la relación de
recurrencia homogénea asociada
an=c1an-1+c2an-2+ …. +ckan-k .
Teorema6.
Suponga que {an} satisface la relación de recurrencia lineal no homogénea:
an=c1an-1+c2an-2+ …. +ckan-k + F(n). Donde c1, c2,....,ck son números reales y
F(n) = (btnt+ bt-1nt-1+ …. + b1n+ b0)sn , donde b0, b1,....,bt y s son números reales.
Cuando s no es una raíz de la ecuación característica de la relación de recurrencia lineal homogénea
lineal asociada, hay una solución particular de la forma:
(ptnt+ pt-1nt-1+ …. + p1n+ p0)sn.
Cuando s es una raíz de la ecuación característica y su multiplicidad es m, hay una solución particular
de la forma:
nm(ptnt+ pt-1nt-1+ …. + p1n+ p0)sn.
Ejemplo1:
Cuál es la solución de la relación de recurrencia an=6an-1-9an-2+F(n) cuando F(n)=3n, F(n)=n3n, F(n)= n2
2n y F(n)=(n2 +1)3n ?
R// De la ecuación de recurrencia lineal homogénea asociada (an=6an-1-9an-2) tenemos que (r-3)2=0,
luego tiene una sola raíz igual a 3, de multiplicidad 2.
Aplicando el teorema6 con respecto a las funciones F(n) indicadas, tenemos las sigtes soluciones
particulares:
• Para F(n)=3n. Dado que s=3=r con multiplicidad 2 (m), entonces: an(p)=n2(p0)3n.
• Para F(n)= n3n. Dado que s=3=r con multiplicidad 2 (m), entonces: an(p)=n2(p1n+ p0)3n.
• Para F(n)= n2 2n. Dado que s=2≠r, entonces: an(p)= (p2n2+ p1n+ p0)2n.
• Para F(n)= n2 2n. Dado que s=2≠r, entonces: an(p)= (p2n2+ p1n+ p0)2n.
• Para F(n)= (n2 +1)3n. Dado que s=3=r multiplic, entonces: an(p)=n2(p2n2+ p1n+ p0)3n.
Matemáticas Discretas II
Capitulo III
Relaciones de recurrencia
Ejemplo2:
Cual es la solución de la relación de recurrencia an=an-1+n que refleja la sumatoria de los primeros n
enteros positivos(Es claro que a1= 1)?
R// Resolviendo su ecuación de recurrencia lineal homogénea asociada (an=an-1) tenemos que (r-1) =0.
Luego an(h)= α(1)n = α, donde α es una constante.
Aplicando el teorema6 con respecto a las funciones F(n)=n para encontrar una solución particular,
tenemos: F(n)=n=n(1)n. Dado que s=1=r con multiplicidad 1. Entonces:
an(p)= n(p1n+ p0)(1)n = n(p1n+ p0) = n2p1+ np0 . Para calcular p1 y p0 tenemos:
an=an-1+n = n2p1+ np0 = (n-1)2p1+ (n-1)p0 +n = n2p1-2np1+p1+np0-p0+n. Por lo tanto:
0 =-2np1+p1-p0+n=n(-2p1+1) +(p1-p0). Luego (-2 p1+1)=0 y (p1-p0)=0. Luego p1=p0=1/2.
Siendo an(p)= n(1/2n+ 1/2)= (n(n+1))/2 una solución particular.
Todas las soluciones de la relación de recurrencia original son:
an=an(p)+an(h)=(n(n+1))/2+α. Como a1=1. Reemplazando 1=(1(1+1))/2+α=1+α. Luego α=0.
Por lo tanto an=an(p)+an(h)=(n(n+1))/2+0 ==(n(n+1))/2
Ejemplo3:
Encuentre todas las soluciones de la relación de recurrencia an=3an-1+2n. cual es la solución con a1=3?
R// De la ecuación de recurrencia lineal homogénea asociada ( an=3an-1) tenemos que an(h)=α3n donde α
es una constante.
Puesto que F(n)=2n, tenemos que s=1≠3=r con multiplicidad 1. Luego an(p)= (p1n+ p0)(1)n. Para
calcular p1 y p0 tenemos:
an= 3an-1+2n = (p1n+ p0) = 3(p1(n-1)+ p0) + 2n
n(2p1+2)+(2p0-3p1) = 0. Por lo tanto:
(2p1+2)=0 y (2p0-3p1)=0. De ahí que p1=-1 y p0=-3/2.
Siendo an(p)= (-n-3/2) una solución particular.
Las soluciones son: an=an(p)+an(h)= (-n-3/2) + α3n.
Como a1=3 se tiene 3=(-1-3/2) + α31. Luego α=11/6.
Por lo tanto an=an(p)+an(h)= (-n-3/2) + (11/6)3n.
Ejemplo4:
Encuentre todas las soluciones de la relación de recurrencia an=5an-1- 6an-2 + 7n.
R// an(h)=α13n+α22n
Puesto que F(n)=7n, tenemos que s=7≠(3 y 2)=r con multiplicidad 1. Luego an(p)= (p0)7n. Para p0
tenemos:
an=5an-1-6an-2+7n = (p0)7n = 5(p07n-1) - 6(p07n-2) + 7n
Entonces p0=49/20. an(p)=(49/20)7n solución particular.
La solución es: an = an(p)+an(h)= (49/20)7n+ α13n + α22n.