Solución:
Sugerencia: comience por el principio, no por el final.
Paso $ 1 $: Si hay un paso, solo hay una forma de subir las escaleras.
Paso $ 2 $: si hay dos pasos, puede dar pasos de $ 2 $ o un paso dos veces, lo que lleva a dos formas de subir las escaleras.
Paso $ 3 $: considere su primer paso, si comienza con $ 1 $ paso, entonces quedan $ 2 $ pasos y sabemos que hay dos formas de subir dos escaleras. Por otro lado, si comienza con escalones de $ 2 $, esto deja un escalón y sabemos que hay una forma de subir un escalón. Esto da $ 1 + 2 = 3 $ formas de subir tres pasos.
Paso $ 4 $: considere el primer paso, si comienza con $ 1 $ paso, entonces quedan $ 3 $ pasos y sabemos que hay tres formas de subir tres escaleras. Por otro lado, si comienza con $ 2 $ pasos, solo quedan dos pasos y sabemos que hay $ 2 $ formas de subir $ 2 $ pasos. Esto le da $ 2 + 3 = 5 $ formas de subir $ 4 $ pasos.
Continúe de esta manera. Es posible que reconozca que los números que obtiene están en una secuencia popular.
He aquí una forma de ver esto visualmente. Dibuja las posibilidades del camino:
En este gráfico dirigido, comienza en el paso 0 y sigue las flechas hasta el paso 11. Las flechas horizontales representan dos pasos y las flechas diagonales representan un paso. Puede ver que si una persona da cada paso, recorrerá el gráfico en zigzag. Si una persona salta tantos pasos como sea posible, viajará principalmente horizontalmente de izquierda a derecha con un paso diagonal en alguna parte.
Ahora vamos a contar las posibilidades comenzando en el paso 10. Solo hay una forma de ir del paso 10 al paso 11, así que escribamos 1 junto al paso 10. Hay dos formas de ir del paso 9 al paso 11, una de esas es hasta el paso 10, así que escribamos 2 junto al paso 9. Desde el paso 8, sus opciones son continuar con los pasos 9 o 10. Desde el paso 9 tiene 2 posibilidades para continuar con el paso 11, y desde el paso 10 solo tiene una . Sumar eso significa que desde el paso 8 tienes 3 posibilidades, así que escribamos 3 junto al paso 8. Continuando hacia atrás, puedes ver que en cada paso, el número de posibilidades es la suma del número de posibilidades de los siguientes dos inmediatos. pasos. Completar esto se ve así:
Ahora puede ver que el número total de posibilidades es 144.
Se puede definir el número de Fibonacci $ n $ -ésimo
como el número de formas en que puede escribir $ n $ como una suma de $ 1 $ y $ 2 $.
Por lo tanto, su respuesta es el número de Fibonacci de $ 11 $ -ésimo.
Tenga en cuenta que hay varias definiciones de los números de Fibonacci de uso común, así que asegúrese de usar la correcta, que coincida con esta definición (tenga en cuenta que $ F_1 = 1, F_2 = 2 $).