de recurrencia homogénea lineal con coeficientes constantes. Dé
el orden de cada relación de recurrencia.
1. an = −3an−1
En los ejercicios 11 al 26, resuelva la relación de recurrencia indicada
para las condiciones iniciales que se señalan.
11. Ejercicio 1; a0= 2
condición inicial a 0 = 1.
16. an = 7an−1 − 10an−2; a0 = 5, a1 = 16
23. La sucesión de Lucas
Ln = Ln−1 + Ln−2, n ≥ 3; L1 = 1, L2 = 3
24. Ejercicio 50, sección 7.1
era 10,000. ¿Cuál era la población en 1970?
en el tiempo n = 0. Suponga que en el tiempo n se introducen
100n venados en sus bosques y que la población aumenta un 20%
cada año. Escriba una relación de recurrencia y una condición inicial que defina la población de venados en el tiempo n y después resuelva la relación de recurrencia. La fórmula siguiente resultará
útil:
Los ejercicios 29 al 33 se refieren a Tito y Samuel, que lanzan monedas
no cargadas. Si las monedas son ambas cara o ambas cruz, Tito gana.
Si una moneda tiene cara y la otra cruz, Samuel gana. Tito comienza
con T monedas y Samuel comienza con S monedas.
si Tito comienza con n monedas. Escriba la relación de recurrencia
para pn.
Samuel.
Algunas veces, una relación de recurrencia que no es una ecuación lineal
homogénea con coeficientes constantes se puede transformar en
una ecuación de este tipo. En los ejercicios 34 y 35, haga las sustituciones
dadas y resuelva la relación de recurrencia que resulta, después
encuentre la solución de la relación de recurrencia original.
34. Resuelva la relación de recurrencia
con condiciones iniciales a0= a1= 1 haciendo la sustitución bn =√an.
35. Resuelva la relación de recurrencia
con condiciones iniciales a0= 8, a1=1/(2√2) tomando logaritmos
en ambos lados y haciendo la sustitución bn= lg an.
En los ejercicios 36 al 38, resuelva la relación de recurrencia para las
condiciones iniciales señaladas.
36. an = −2nan−1 + 3n(n − 1)an−2; a0 = 1, a1 = 2
37.
38. A(n, m) = 1+ A(n−1, m−1)+ A(n−1, m), n−1 ≥ m ≥ 1,
n ≥ 2; A(n, 0) = A(n, n) = 1, n ≥ 0
39. Demuestre que
donde f denota la sucesión de Fibonacci.
se llama relación de recurrencia lineal no homogénea de segundo
orden con coeficientes constantes.
Sea g(n) una solución de (7.2.20). Demuestre que cualquier
solución U de (7.2.20) es de la forma
Un = Vn + g(n),
donde V es una solución de la ecuación homogénea (7.2.13).
Si f (n) = C en (7.2.20), se puede demostrar que g(n) = C en (7.2.21)
si 1 no es una raíz de
t2 − c1t − c2 = 0,
g(n) = C n si 1 es una raíz de (7.2.22) de multiplicidad uno, y g(n) =
C n2 si 1 es una raíz de (7.2.22) de multiplicidad dos. De manera similar,
si f(n) = Cn, se puede demostrar que g(n) = C 1n + C 0 si 1 no es
una raíz de (7.2.22), g(n) = C 1n2 + C 0n si 1 es una raíz de multiplicidad
uno, y g(n) = C 1n3 + C 0n2 si 1 es una raíz de multiplicidad dos.
Si f (n) = Cn2, se puede demostrar que g(n) = C 2n2 + C 1n + C 0 si 1
no es una raíz de (7.2.22), g(n) = C 2n3 + C 1n2 + C 0n si 1 es una raíz
de multiplicidad uno y g(n) = C 2n4 + C 1n3 + C
0n2 si 1 es una raíz de multiplicidad dos. Si f(n) = Cn, se puede demostrar que g(n) = C Cn si
C no es una raíz de (7.2.22), g(n) = C nC n si C es una raíz de multiplicidad
uno, y g(n) = C n2Cn si C es una raíz de multiplicidad dos. Las
constantes se pueden determinar sustituyendo g(n) en la relación de recurrencia
e igualando los coeficientes de los dos lados de la ecuación
resultante. Como ejemplos, los términos constantes en los dos lados de
la ecuación deben ser iguales, y el coeficiente de n en el lado izquierdo
de la ecuación debe ser igual al coeficiente de n en el lado derecho
de la ecuación.
A partir de estos hechos y del ejercicio 40, encuentre las
soluciones generales de las relaciones de recurrencia de los ejercicios
41 al 46
41. an =6an−1 − 8an−2 + 3
an = f (n)an−1 + g(n)an−2
se llama relación de recurrencia lineal homogénea de segundo
orden. Los coeficientes f (n) y g (n) no son necesariamente constantes.
Demuestre que si S y T son soluciones de (7.2.23), entonces
bS + dT también es una solución de (7.2.23).
t2 − c1t − c2 = 0
son iguales a r, y suponga que an satisface
an = c1an−1 + c2an−2, a0 = C0, a1 = C1.
Demuestre que existen constantes b y d tales que
an = brn + dnrn, n = 0, 1, . . . ,
para completar así la prueba del Teorema 7.2.14.
problema de comunicación de n nodos (vea el ejercicio 48, sección
7.1). Use iteraciones para demostrar que an
≤ 2n − 4, n ≥ 4.
El juego de la Torre de Hanoi con cuatro estacas y n discos tiene las
mismas reglas que el de tres estacas; la única diferencia es que se tiene
una estaca adicional. Los ejercicios 50 al 53 se refieren al siguiente
algoritmo para resolver el juego de la Torre de Hanoi con cuatro
estacas y n discos.
Suponga que las estacas están numeradas 1, 2, 3, 4 y que el problema
es mover los discos, que inicialmente están apilados en la estaca
1, a la estaca 4. Si n = 1, se mueve el disco a la estaca 4 y se detiene.
Si n > 1, sea kn el entero más grande que satisface
Se fijan kn discos hasta abajo de la estaca 1. Se invoca este algoritmo
en forma recursiva para mover los n − kn discos hasta arriba de la estaca
1 a la estaca 2. Durante esta parte del algoritmo, los kn discos de
abajo en la estaca 1 permanecen fijos. Después se mueven los kn discos
de la estaca 1 a la estaca 4 invocando el algoritmo óptimo de tres estacas
(vea el ejemplo 7.1.8) y usando sólo las estacas 1, 3 y 4. Por último,
de nuevo en forma recursiva, se invoca este algoritmo para mover
los n − kn discos de la estaca 2 a la 4. Durante esta parte del algoritmo,
los kn discos en la estaca 4 están fijos. Sea T(n) el número de movimientos
requeridos por este algoritmo.
Este algoritmo, aunque no se sabe que sea óptimo, usa tan
pocos movimientos como cualquier otro algoritmo que se haya
propuesto para el problema de cuatro estacas.
50. Derive la relación de recurrencia
T (n) = 2T (n − kn) + 2kn − 1.
51. Calcule T(n) para n = 1, . . . , 10. Compare estos valores con el número
óptimo de movimientos para resolver el problema de tres estacas.
52. Sea
Usando inducción o de otra manera, pruebe que
T (n) = (kn + rn − 1)2kn + 1.
53. Demuestre que T (n) = O(4√n).
54. Dé un algoritmo óptimo para resolver la variante de la Torre de
Hanoi en donde se permite una pila de discos, excepto por la pila
inicial y final, siempre que el disco más grande esté hasta abajo
(los discos arriba del disco más grande en la pila pueden tener el
orden que sea). El problema es transferir los discos a otra estaca
moviendo un disco a la vez comenzando con todos los discos apilados
en una estaca en orden del más grande (abajo) al más pequeño
como en el juego original. La posición final será la misma que
en el juego original: los discos se apilan en orden del más grande
(abajo) al más pequeño. Pruebe que su algoritmo es óptimo. Este
problema se debe a John McCarthy.
