2. Haga el seguimiento del algoritmo 4.4.4 cuando n = 4 y el cuadro
que falta está en la esquina superior izquierda del cuadrado.
3. Dé seguimiento al algoritmo 4.4.4 cuando n = 8 y el cuadrado que
falta está a cuatro cuadros de la izquierda y a seis del borde superior.
4. Demuestre que el algoritmo 4.4.4 es correcto.
5. Dé seguimiento al algoritmo 4.4.6 para n = 4.
6. Haga el seguimiento del algoritmo 4.4.6 para n = 5.
7. Pruebe que el algoritmo 4.4.6 es correcto.
8. Pruebe que
walk(n) = fn+1 para toda n ≥ 1.
9. a) Use las fórmulas s1 = 1, sn = sn−1 + n para toda n ≥ 2,
para escribir un algoritmo recursivo que calcule
sn= 1 + 2 + 3 + . . . n.
b) Dé una prueba usando inducción matemática de que su algoritmo
del inciso a) es correcto.
10. a) Use las fórmulas s1 = 2, sn = sn−1 + 2n para toda n ≥ 2,
para escribir un algoritmo recursivo que calcule
sn
= 2 + 4 + 6 + . . . 2n.
b) Dé una prueba usando inducción matemática de que su algoritmo
del inciso a) es correcto.
11. a) Un robot puede dar pasos de 1, 2 o 3 metros. Escriba un algoritmo
recursivo que calcule el número de maneras en que el robot
puede caminar n metros.
b) Dé una prueba usando inducción matemática de que su algoritmo
del inciso a) es correcto.
12. Escriba un algoritmo recursivo para encontrar el mínimo de una sucesión finita de números. Dé una prueba con inducción matemática
de que su algoritmo es correcto.
13. Escriba un algoritmo recursivo para encontrar el máximo de una
sucesión finita de números. Dé una prueba usando inducción matemática
de que su algoritmo es correcto.
14. Escriba un algoritmo recursivo que invierta una sucesión finita.
Proporcione una prueba usando inducción matemática de que su
algoritmo es correcto.
15. Escriba una algoritmo no recursivo para calcular n!.
16. Un robot puede dar pasos de 1 o 2 metros. Escriba un algoritmo para
numerar todas las maneras en que el robot puede caminar n metros.
17. Un robot puede dar pasos de 1, 2 o 3 metros. Escriba un algoritmo para
numerar todas las maneras en que un robot puede caminar n metros.
Los ejercicios 18 al 32 se refieren a la sucesión de Fibonacci {fn}.
18. Suponga que al inicio del año hay un par de conejos y que cada
mes cada par produce un nuevo par que se convierte en productivo
después de un mes. Suponga, además, que no ocurren muertes.
Sea an el número de pares de conejos al final del mes n. Demuestre
que a1
= 1, a2
= 2 y an
− an−1
= an −2. Pruebe que an
= fn+1
para toda n ≥ 1.
19. La pregunta original de Fibonacci era: En las condiciones del ejercicio
18, ¿cuántos pares de conejos hay después de un año? Responda
a la pregunta de Fibonacci.
20. Demuestre que el número de maneras para enlosar un tablero de
2 × n con piezas rectangulares de 1 × 2 es fn+1, el n ésimo número
de Fibonacci.
21. Use inducción matemática para demostrar que
para toda n ≥ 2.
22. Demuestre que
para toda n ≥ 1.
23. Demuestre que
para toda n ≥ 3.
24. Use inducción matemática para demostrar que
para toda n ≥ 1.
25. Use inducción matemática para demostrar que
para toda n ≥ 2.
26. Use inducción matemática para demostrar que para toda n ≥ 1, fn
es par si y sólo si n es divisible entre 3.
27. Use inducción matemática para demostrar que para toda n ≥ 6,
28. Use inducción matemática para demostrar que para toda n ≥ 1,
29. Use inducción matemática para demostrar que para toda n ≥ 1,
30. Use inducción matemática para demostrar que todo entero n ≥ 1
se puede expresar como la suma de números de Fibonacci distintos,
sin que haya dos consecutivos.
31. Demuestre que la representación en el ejercicio 30 es única si no
se permite f1 como sumando.
32. Demuestre que para toda n ≥ 2,
Observe que esta fórmula da fn en términos de un predecesor en
lugar de dos predecesores como en la definición original.
33. [Requiere cálculo]. Suponga la fórmula para diferenciar productos:
Use inducción matemática para probar que
34. [Requiere cálculo]. Explique cómo la fórmula da un algoritmo recursivo
para integrar logn |x|:
Dé otros ejemplos de fórmula de integración recursivas.
