Nombre: Cueto A. Luis F. C.I.: 13378303
Nomenclatura:
Se usará Fn para indicar
el n-esimo número de fibonacci.
En este ejercicio Fn indica el número de maneras diferentes de
subir la escalera dado n escalones y n es un entero positivo.
Antecedentes:
Este problema es parecido en su
forma, al problema planteado por Liber Abacci y cuyo enunciado aparece en la
página 102 del Libro de José Rodríguez.
Pregunta : (
Ejercicio # 42 del capítulo 3):
Considere una escalera de n
escalones, ¿De cuantas maneras diferentes puede ir una persona del primero al
último escalón , si ella va de uno en uno escalón o de dos en dos escalones.
Respuesta:
Si el # de escalones es 1 (n = 1)
Solo hay una forma de subir un solo
escalón, se sobre entiende que un solo escalón no lo puedo subir de dos en dos.
Por tanto F1 = 1
Si el # de escalones es 2 (n = 2)
Las maneras diferentes de subir la escalera
son:
11 si es de uno en uno
2 si es de dos en dos
Por lo tanto F2 = 2
Si el # de escalones es 3 (n = 3)
Las maneras diferentes de subir la escalera
son:
111 si es de uno en uno
12 si se sube el primero de uno en uno y los
restantes de dos en dos
21 si se suben de dos en dos los primeros y de
uno en uno el que resta.
Por tanto F3 = 3
Si se continua con este proceso todo indica que
el número de maneras diferentes en que subir una escalera de n escalones esta
dado por el número fibonacci. Aplicando inducción matemática para probar el
caso general se tiene:
Fn = Fn-1+ Fn-2
con F2 = 2 y F1= 1 con n >= 3
Caso Base: F3 = F2 + F1
=> F3 = 3
Paso Inductivo: Fn + 1 =
Fn + Fn-1
Fn = Fn-1 + Fn-2
Fn +1= Fn + Fn-1
Fn + Fn+1= Fn
+ Fn-1 + Fn-2 + Fn-1
Fn+1 = Fn + Fn-1
Note que los Fn se
cancelan y por definición Fn = Fn-1 + Fn-2 .
Por
tanto el número de
maneras de subir la escalera de n escalones
obedece a la recurrencia de
fibonacci.
Moraleja:
Los números de fibonacci se pueden aplicar para
simular situaciones muy variadas.