DiscII 3

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 8

Matemáticas Discretas II

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.

Ejemplo4: Interés compuesto


Suponga que una persona deposita $ 10.000 en una cuenta de ahorros en un banco que produce
rendimientos del 11% de interés compuesto anual. Cuánto se tendrá ahorrado al cabo de 30 años ?
R// Sea Pn la cantidad de dinero luego de n años. Vemos que {Pn} satisface la relación de recurrencia
Pn=(1.11)Pn-1 . En el caso anterior podemos calcular una formula iterativa que nos permita hallar Pn.
Pues:
P1 = (1.11)P0
P2 = (1.11)P1 = (1.11) (1.11)P0 = (1.11)2 P0
P3 = (1.11)P2 = (1.11) (1.11)2 P0 = (1.11)3 P0. Es fácil ver que Pn = (1.11)n P0.
Luego para el problema en cuestión P30 = (1.11)30 (10.000) = $ 228.922,97.
Matemáticas Discretas II
Capitulo III
Relaciones de recurrencia

Ejemplo5: Los conejos y la secuencia de fibonaci


Una joven pareja de conejos es colocada en una isla. Un par de conejos no se reproduce hasta que tiene
2 meses de edad. Después que estos tienen los 2 meses de edad, cada par produce un nuevo par.
Encuentre una relación de recurrencia para el numero de pares de conejos en la isla al cabo de n meses,
asumiendo que ningún conejo muere.
R// Denotaremos por fn el numero de conejos después de n meses.
Notemos que al finalizar el primer mes el numero de pares es f1=1 Porque ?
Igualmente al finalizar el segundo mes el numero de pares es f2=1 Porque ?
Para encontrar el numero de pares después de n meses adicione al numero de parejas en el mes previo
fn-1 el numero pares recién nacidos el cual es equivalente a fn-2, puesto que cada par recién nacido viene
de un par de al menos 3 meses de edad. Consecuentemente {fn} satisface la relación de recurrencia:
fn = fn-1 + fn-2 para n≥3. (secuencia de fibonaci)

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.

Ejemplo7: enumeración de claves


Un sistema de computador considera una cadena de dígitos decimales valida si contiene un numero par
de dígitos 0. Sea an el numero de claves validas de n dígitos. Encuentre una relación de recurrencia para
an .
R// El numero de cadenas de 1 dígitos es 9 (ai =9) (todos los dígitos exceptuando al propio 0)
Para que una cadena de n dígitos se forme a partir de una cadena de n-1 dígitos se debe cumplir lo
siguiente:
• Si hay an-1 cadenas validas de longitud n-1 dígitos, entonces se pueden formar cadenas de longitud
n, adicionando a cada una de estas los 9 dígitos restantes. Es decir se formarían 9an-1 nuevas
cadenas
• A las cadenas de longitud n-1 no validas (10n-1-an-1) se les podría adicionar un 0, para crear cadenas
de longitud n validas. Es decir se formarían (10n-1-an-1) nuevas cadenas.
Matemáticas Discretas II
Capitulo III
Relaciones de recurrencia

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)

Ejercicios: Rosen sección 6.1 del 1 al 15


Matemáticas Discretas II
Capitulo III
Relaciones de recurrencia

Solucionando relaciones de recurrencia


Definición 1
Una relación de recurrencia de grado k con coeficientes constantes es una relación de recurrencia de la
forma:
an= c1an-1 + c2an-2 + …. +ckan-k .
Donde c1, c2, …. ck son números reales, y ck≠0.

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 ?

Solucionando ecuaciones de recurrencia homogéneas con coeficientes


constantes
La primera alternativa consiste en buscar soluciones de la forma an= rn, donde r es una constante. Note
que an=rn es una solución de la relación de recurrencia an=c1an-1+c2an-2+ …. +ckan-k si y
solo si:
rn=c1rn-1+c2rn-2+ …. +ckrn-k.
Cuando dividimos ambos lados por rn-k y reacomodamos para que la ecuación resultante sea igualada a
0, obtenemos la siguiente ecuación:
rk - c1rk-1 - c2rk-2 - …. - ck-1r - ck = 0. (ecuación característica)
Consecuentemente, la secuencia { an } con an= rn es una solución si y solo si r es una solución de la
ecuación característica. Las soluciones de esta ecuación son llamadas las raíces características de la
relación de recurrencia..

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

Ejemplo2: Formula explícita para la secuencia de fibonaci


Dado que la ecuación de recurrencia de esta es:
fn = fn-1+ fn-2 y se satisfacen las condiciones iniciales
f0 = 0 y f1 = 1. verificar que la formula explícita para hallar dicha relación de recurrencia es:
n n
1 1 + 5  1 1− 5 
f n
= 
5 2 
 −  
5  2 

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

Relaciones de recurrencia lineal no homogéneas con coeficientes


constantes

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.

Ejercicios: Rosen sección 6.2 del 1 al 19

También podría gustarte