Autoexamen 1. Una definición recursiva de una sucesión consiste en una y de . 2. Una relación de recurrencia es una ecuación que define cada úl...

Autoexamen
1. Una definición recursiva de una sucesión consiste en una

y de .
2. Una relación de recurrencia es una ecuación que define cada
último término de una sucesión en función de los de la
sucesión.
3. Las condiciones iniciales para una definición recursiva de una
sucesión compuesta de uno o más de los de la sucesión.
4. Resolver un problema de forma recursiva significa dividir el
problema en subproblemas más pequeños del mismo tipo que el
problema inicial, al suponer y encontrar cómo utilizar la
suposición para .
5. Un paso crucial para resolver un problema de forma recursiva
es definir una en términos de la cual está la relación de
recurrencia y las condiciones iniciales dadas.
Conjunto de ejercicios 5.6
Encuentre los cuatro primeros términos de cada una de las sucesiones
definidas recursivamente en los ejercicios 1 al 8.
1. ak 2ak฀1 k, para todo entero k 2
a1 1
2. bk bk฀1 3k, para todo entero k 2
b1 1
3. ck k ck฀1
2, para todo entero k 1
c0 1
4. dk k dk฀1
2, para todo entero k 1
d0 3
5. sk sk฀1 2sk฀2, para todo entero k 2
s0 1 s1 1
6. tk tk฀1 2tk฀2, para todo entero k 2
t0 ฀ 1 t1 2
7. uk kuk฀1 ฀ uk฀2, para todo entero k 3
u1 1 u2 1
8. k k฀1 k฀2 1, para todo entero k 3
1 1 2 3
9. Sea a0, a1, a2, . . . definida por la fórmula an 3n 1, para todo
entero n 0. Demuestre que esta sucesión satisface la relación
de recurrencia ak ak฀1 3, para todo entero k 1.
10. Sea b0, b1, b2, . . . definida por la fórmula bn 4n, para todo
entero n 0. Demuestre que esta sucesión satisface la relación
de recurrencia bk 4 bk ฀ 1, para todo entero k 1.
11. Sea c0, c1, c2, . . . definida por la fórmula cn 2n ฀ 1 para todo
entero n 0. Demuestre que esta sucesión satisface la relación
de recurrencia
ck 2ck ฀ 1 1.
12. Sea s0, s1, s2, . . . definida por la fórmula sn = (−1)n
n! , para todo
entero n 0. Demuestre que esta sucesión satisface la relación
de recurrencia
sk =
−sk−1
k
.
13. Sea t0, t1, t2, . . . definida por la fórmula tn 2 n, para todo
entero n 0. Demuestre que esta sucesión satisface la relación
de recurrencia
tk 2tk ฀ 1 ฀ tk ฀ 2.
14. Sea d0, d1, d2, . . . definida por la fórmula dn 3n ฀ 2n, para todo
entero n 0. Demuestre que esta sucesión satisface la relación
de recurrencia
dk 5dk ฀ 1 ฀ 6dk ฀ 2.
15. Para la sucesión de los números de Catalan definidos en el
ejemplo 5.6.4, demuestre que para todo entero n 1,
Cn = 1
4n + 2
(2n + 2
n + 1
).
16. Use la relación de recurrencia y los valores de la sucesión de
la Torre de Hanoi m1, m2, m3, . . . analizada en el ejemplo 5.6.5
calcule m7 y m8.
17. Torre de Hanoi con requisito de adyacencia: Supongamos que,
además del requisito de nunca mover un disco más grande en la
parte superior a uno más pequeño, los sacerdotes que mueven los
discos de la Torre de Hanoi también están autorizados sólo para
mover los discos uno por uno de un poste a un poste adyacente.
Suponga que los postes A y C están en los dos extremos de la
fila A y que el poste B está en el centro. Sea
an
el número mínimo de movimientos
necesarios para transferir de una
torre de n discos del poste A al
poste C
.
a. Determine a1, a2 y a3. b. Encuentre a4.
c. Encuentre una relación de recurrencia para a1, a2, a3, . . . .
18. Torre de Hanoi con requisito de adyacencia: Supongamos que
la misma situación que en el ejercicio 17. Sea
an
el número mínimo de movimientos
necesarios para la transferencia de
una torre de n discos del poste A
al poste B
.
a. Determine b1, b2 y b3. b. Encuentre b4.
c. Demuestre que bk ak ฀ 1 1 bk ฀ 1 para todo entero
k 2, donde a1, a2, a3, . . . es la sucesión definida en el ejercicio
17.
d. Demuestre que bk 3 bk ฀ 1 1 para todo entero k