En los ejercicios 1 al 3, encuentre una relación de recurrencia y condiciones
iniciales que generen una sucesión que comience con los términos
dados.
1. 3, 7, 11, 15, . . .
2. 3, 6, 9, 15, 24, 39, . . .
3. 1, 1, 2, 4, 16, 128, 4096, . . .
En los ejercicios 4 al 8, suponga que una persona invierte $2000 al
14% de interés anual compuesto. Sea An la cantidad al final de n
años.
4. Encuentre una relación de recurrencia para la sucesión A0, A1, . . . .
5. Encuentre una condición inicial para la sucesión A0, A1, . . . .
6. Encuentre A1, A2 y A3.
7. Encuentre una fórmula explícita para An.
8. ¿Cuánto tiempo tomará que una persona duplique su inversión inicial?
Si una persona invierte en una anualidad con amparo tributario, el dinero
invertido, igual que el interés ganado, no está sujeto a gravamen
sino hasta que se retira de la cuenta. En los ejercicios 9 al 12, suponga
que una persona invierte $2000 cada año en una anualidad con amparo
tributario a un interés del 10% anual compuesto. Sea An la
cantidad de dinero al final de n años.
9. Encuentre una relación de recurrencia para la sucesión A0, A1, . . . .
10. Encuentre una condición inicial para la sucesión A0, A1, . . . .
11. Encuentre A1, A2 y A3.
12. Encuentre una fórmula explícita para An.
En los ejercicios 13 al 17, suponga que una persona invierte $3000 al
12% de interés compuesto cada trimestre. Sea An la cantidad al final de
n años.
13. Encuentre una relación de recurrencia para la sucesión A0, A1, . . . .
14. Encuentre una condición inicial para la sucesión A0, A1, . . . .
15. Encuentre A1, A2 y A3.
16. Encuentre una fórmula explícita para An.
17. ¿Cuánto tiempo tomará que una persona duplique la inversión inicial?
18. Sea Sn el número de cadenas de n bits que no contienen el patrón
000. Encuentre una relación de recurrencia y condiciones iniciales
para la sucesión {Sn}.
Los ejercicios 19 al 21 se refieren a la sucesión S donde Sn denota el
número de cadenas de n bits que no contienen el patrón 000.
19. Encuentre una relación de recurrencia y condiciones iniciales para
la sucesión {Sn}.
20. Demuestre que Sn= fn+2, n = 1, 2, . . . , donde f denota la sucesión
de Fibonacci.
21. Considerando el número de cadenas de n bits con exactamente i
ceros y el ejercicio 20, demuestre que
donde f denota la sucesión de Fibonacci.
Los ejercicios 22 al 24 se refieren a la sucesión S1, S2, . . . , donde Sn
denota el número de cadenas de n bits que no contienen el patrón 010.
22. Calcule S1, S2, S3 y S4.
23. Considerando el número de cadenas de n bits que no contienen el
patrón 010 y que no comienzan con 0 (es decir, comienzan con 1);
que comienzan con un 0 (es decir, comienzan con 01); que comienzan
con dos ceros, etcétera, derive la relación de recurrencia
Sn = Sn−1 + Sn−3 + Sn−4 + Sn−5 +· · ·+ S1 + 3.
24. Sustituyendo n por n − 1 en (7.1.14), escriba una fórmula para
Sn−1. Reste la fórmula para Sn−1 de la fórmula para Sn y utilice el
resultado para derivar la relación de recurrencia
Sn = 2Sn−1 − Sn−2 + Sn−3.
En los ejercicios 25 al 30, C0, C1, C2, . . . denota la sucesión de números
de Catalan.
25. Dado que C0= C1= 1 y C2= 2, calcule C3, C4 y C5 usando la relación
de recurrencia del ejemplo 7.1.7.
26. Demuestre que los números de Catalan están dados por la relación
de recurrencia
(n + 2)Cn+1 = (4n + 2)Cn, n ≥ 0,
y la condición inicial C0= 1.
27. Pruebe que
28. Derive una relación de recurrencia y una condición inicial para el
número de maneras de colocar paréntesis en el producto
a1 ∗ a2 ∗ · · · ∗ an, n ≥ 2.
Ejemplos: Existe una manera de colocar paréntesis en a1 * a2, a saber
(a1 * a2). Existen dos maneras de colocar paréntesis en a1 * a2 *
a3, a saber, ((a1 * a2) * a3) y (a1 * (a2 * a3)). Deduzca que el número
de maneras de colocar paréntesis en el producto de n elementos
es Cn−1, n ≥ 2.
29. Derive una relación de recurrencia y una condición inicial para el
número de maneras de dividir un polígono convexo de (n + 2) lados,
n ≥ 1, en triángulos dibujando n − 1 líneas a través de los
vértices que no se cruzan en el interior del polígono. (Un polígono
es convexo si cualquier línea que une dos puntos del polígono
está completamente contenida en el polígono). Por ejemplo, existen
cinco maneras de dividir un pentágono convexo en triángulos
dibujando dos líneas que no se cruzan a través de los vértices.
Deduzca que el número de maneras de dividir un polígono convexo
de (n + 2) lados en triángulos dibujando n − 1 líneas que no se
cruzan a través de los vértices es Cn, n ≥ 1.
30. Dividiendo las rutas de la esquina inferior izquierda a la esquina
superior derecha en una rejilla de (n + 1)×(n + 1), donde el movimiento
está restringido sólo a la derecha o arriba, en clases basadas
en la primera vez que la ruta llega a la diagonal que va de
la esquina inferior izquierda a la superior derecha, después de salir
de la esquina inferior izquierda, derive la relación de recurrencia
En los ejercicios 31 y 32, sea Sn el número de rutas desde la esquina
inferior izquierda de una rejilla de n × n a la esquina superior derecha,
donde el movimiento está restringido a la derecha, arriba o en
diagonal al noreste [es decir, de (i, j) a (i + 1, j + 1)] y donde se permite
tocar pero no cruzar la diagonal de la esquina inferior izquierda
a la superior derecha. Los números S0, S1, . . . se llaman números de
Schröeder.
31. Demuestre que S0= 1, S1= 2, S2= 6 y S3= 22.
32. Derive una relación de recurrencia para la sucesión de Schröeder.
33. Escriba las soluciones explícitas para el juego de la Torre de Hanoi
para n = 3, 4.
34. ¿A qué valores tienden el precio y la cantidad en el ejemplo 7.1.9
cuando b < k?
35. Demuestre que cuando b < k en el ejemplo 7.1.9, el precio tiende
al dado por la intersección de las curvas de oferta y demanda.
36. Demuestre que cuando b > k en el ejemplo 7.1.9, las diferencias
entre precios sucesivos aumentan.
Los ejercicios 37 al 43 se refieren a la función de Ackermann A(m, n).
37. Calcule A(2, 2) y A(2, 3).
38. Utilice inducción para demostrar que
A(1, n) = n + 2, n = 0, 1, . . . .
39. Utilice inducción para demostrar que
A(2, n) = 3 + 2n, n = 0, 1 . . . .
40. Suponga una fórmula para A(3, n)y pruébela por inducción.
41. Pruebe que A(m, n) > n para toda m ≥ 0, n ≥ 0 por inducción sobre
m. El paso inductivo usará inducción sobre n.
42. Usando el ejercicio 41 o de otra manera, pruebe que A(m, n) > 1
para toda m ≥ 1, n ≥ 0.
43. Usando el ejercicio 41 o de otra manera, pruebe que A(m, n) <
A(m, n + 1) para toda m ≥ 0, n ≥ 0.
Lo que hemos llamado la función de Ackermann, en realidad se deriva
de la función de Ackermann original definida por
AO(0, y, z)=z + 1, y, z ≥ 0,
AO(1, y, z)=y + z, y, z ≥ 0,
AO(2, y, z)=yz, y, z ≥ 0,
AO(x + 3, y, 0)=1, x, y ≥ 0,
AO(x + 3, y, z + 1)=
AO(x + 2, y, AO(x + 3, y, z)), x, y, z ≥ 0.
Los ejercicios 44 al 47 se refieren a la función AO y a la función de Ackermann
A.
44. Demuestre que A(x, y) = AO(x, 2, y + 3) − 3 para y ≥ 0 y x= 0, 1, 2
45. Demuestre que AO(x, 2, 1) = 2 para x ≥ 2.
46. Demuestre que AO(x, 2, 2) = 4 para x ≥ 2.
47. Demuestre que para x, y ≥ 0.
48. Una red consiste en n nodos. Cada nodo tiene instalaciones de comunicaciones
y almacenamiento local. Periódicamente, todos los
archivos deben compartirse. Un enlace consiste en dos nodos que
comparten archivos. En particular, cando los nodos A y B se enlazan,
A transmite todos sus archivos a B y B transmite todos sus archivos
a A. sólo existe un enlace a la vez, y después de establecer
un enlace y compartir archivos, el enlace se elimina. Sea an el número
mínimo de enlaces requerido por n nodos para que todos los
archivos estén disponibles para todos lo nodos.
a) Demuestre que a2= 1, a3≤ 3, a4≤ 4.
b) Demuestre que an ≤ an−1 + 2, n ≥ 3.
49. Si Pn denota el número de permutaciones de n objetos diferentes,
encuentre una relación de recurrencia y una condición inicial para
la sucesión P1, P2, . . . .
50. Suponga que tiene n dólares y que cada día compra ya sea jugo de
naranja ($1), leche ($2) o cerveza ($2). Si Rn es el número de maneras
de gastar todo el dinero, demuestre que
Rn = Rn−1 + 2Rn−2.
Tome en cuenta el orden. Por ejemplo, hay 11 maneras de gastar
$4: LC, CL, NNL, NNC, NLN, NCN, LNN, CNN, NNNN, LL, CC.
51. Suponga que tiene n dólares y que cada día compra ya sea cinta
adhesiva ($1), papel ($1), plumas ($2), lápices ($2) o clips ($3). Si
Rn es el número de maneras de gastar todo el dinero, derive una relación
de recurrencia para la sucesión R1, R2, . . . .
52. Sea Rn el número de regiones en las que se divide el plano por n
líneas. Suponga que cada par de líneas se unen en un punto, pero
que nunca se unen tres líneas en un punto. Derive una relación de
recurrencia para la sucesión R1, R2, . . . .
Los ejercicios 53 y 54 se refieren a la sucesión Sn definida por
53. Calcule S3 y S4.
54. Suponga una fórmula para Sn y use inducción matemática para demostrar
que es correcta.
55. Sea Fn el número de funciones f de X = {1, . . . , n} en X que tiene
la propiedad de que si i está en el recorrido de f, entonces 1, 2, . . . ,
i − 1 también están en el recorrido de f. (Haga F0= 1.) Demuestre
que la sucesión F0, F1, . . . satisface la relación de recurrencia
56. Si α es una cadena de bits, sea C(α) el número máximo de ceros
consecutivos en α. [Ejemplos: C(10010) = 2, C(00110001) = 3].
Sea Sn el número cadenas α de n bits con C(α) ≤ 2. Desarrolle una
relación de recurrencia para S1, S2, . . . .
57. La sucesión g1, g2, . . . se define por la relación de recurrencia
gn = gn−1 + gn−2 + 1, n ≥ 3,y las condiciones iniciales g1 = 1, g2 = 3.
Utilizando inducción matemática o de otra manera, demuestre que
gn = 2 fn+1 − 1, n ≥ 1,
donde f1, f2, . . . es la sucesión de Fibonacci.
58. Considere la fórmula
y la condición inicial u1
= 1. Explique por qué la fórmula no es
una relación de recurrencia. Una conjetura desde hace mucho
tiempo es que para todo entero positivo n, un está definida y es
igual a 1. Calcule un para n = 2, . . . , 7.
59. Defina la sucesión t1, t2, . . . por la relación de recurrencia
tn = tn−1tn−2, n ≥ 3,
y condiciones iniciales
t1 = 1, t2 = 2.
¿Qué está mal en la siguiente “demostración” de que tn= 1 para
toda n ≥ 1?
Paso base Para n = 1, se tiene t1= 1; entonces, el paso base se
verifica.
Paso inductivo Suponga que tk= 1 para k < n. Debemos probar
que tn= 1. Ahora
tn = tn−1tn−2
= 1 · 1 por la suposición inductiva
= 1.
El paso inductivo queda completo.
60. Derive una relación de recurrencia para C(n, k), el número de subconjuntos
de k elementos de un conjunto de n elementos. En particular,
escriba C(n + 1, k) en términos de C(n, i) para la i apropiada.
61. Derive una relación de recurrencia para S(k, n), el número de maneras
de elegir k elementos, con repeticiones permitidas, de n tipos
disponibles. En particular, escriba S(k, n) en términos de S(k− 1, i) para la i apropiada.
62. Sea S(n, k) el número de funciones de {1, . . . , n} sobre {1, . . . , k}.
Demuestre que S(n, k) satisface la relación de recurrencia
63. La sucesión de Lucas L1, L2, . . . (llamada así en honor de Édouard
Lucas, inventor del juego de la Torre de Hanoi) se define por la relación
de recurrencia
Ln = Ln−1 + Ln−2, n ≥ 3,
y las condiciones iniciales
L1 = 1, L2 = 3.
a) Encuentre los valores de L3, L4 y L5.
b) Demuestre que
Ln+2 = fn+1 + fn+3, n ≥ 1,
donde f1, f2, . . . denotan la sucesión de Fibonacci.
64. Establezca la relación de recurrencia
sn+1,k = sn,k−1 + nsn,k
para los números de Stirling del primer tipo (vea el ejercicio 81,
sección 6.2).
65. Establezca la relación de recurrencia
Sn+1,k = Sn,k−1 + kSn,k
para los números de Stirling del segundo tipo (vea ejercicio 82,
sección 6.2).
66. Demuestre que
donde Sn,k denota un número de Stirling del segundo tipo (vea ejercicio
82, sección 6.2).
67. Suponga que una persona invierte una suma de dinero a r % de interés
anual compuesto. Explique la regla general: Para estimar el
tiempo para duplicar la inversión, divida 70 entre r.
68. Derive una relación de recurrencia para el número de multiplicaciones
necesarias para evaluar un determinante de n × n por el
método de cofactores.
Una permutación de sube/baja es una permutación p de 1, 2, . . . , n
que satisface
p(i ) < p(i + 1) para i = 1, 3, 5, . . .
y
p(i ) > p(i + 1) para i = 2, 4, 6, . . . .
Por ejemplo, hay cinco permutaciones sube/baja de 1, 2, 3, 4:
1, 3, 2, 4; 1, 4, 2, 3; 2, 3, 1, 4;
2, 4, 1, 3; 3, 4, 1, 2.
Sea En el número de permutaciones sube/baja de 1, 2, . . . , n. (Defina= E0= 1). Los números E0, E1, E2, . . . se llaman números de Euler.
69. Liste todas las permutaciones sube/baja de 1, 2, 3. ¿Cuál es el valor
de E3?
70. Liste todas las permutaciones sube/baja de 1, 2, 3, 4, 5. ¿Cuál es
el valor de E5?
71. Demuestre que en una permutación sube/baja de 1, 2, . . . , n, n
debe ocurrir en la posición 2i, para alguna i.
72. Use el ejercicio 71 para derivar la relación de recurrencia.
73. Considerando dónde debe ocurrir 1 en una permutación sube/baja,
derive la relación de recurrencia
74. Pruebe que
