Es de esos problemas que invitan a enumerar caminos uno por uno. Hay una manera mucho más elegante de resolverlo.
Escalera de 12 peldaños
Enunciado
Subes una escalera de 12 peldaños. En cada movimiento puedes avanzar 1 o 2 peldaños.
¿De cuántas maneras distintas puedes llegar arriba?
Ver solución
Solución
Respuesta: 233 formas.
Sea F(n) el número de maneras de llegar al peldaño n.
El último movimiento solo puede ser de dos tipos:
- o vienes del peldaño n-1 con un salto de 1;
- o vienes del peldaño n-2 con un salto de 2.
Por tanto,
$
F(n)=F(n-1)+F(n-2).
$
Las condiciones iniciales son:
$
F(1)=1,\qquad F(2)=2.
$
A partir de ahí:
$
1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ 233.
$
Así, para 12 peldaños,
$
F(12)=233.
$
Es la misma recurrencia de Fibonacci, pero desplazada por las condiciones iniciales.