¿Cuántas maneras distintas de subir escaleras en 1 o 2 pasos a la vez? (Rompecabezas de Fibonacci)

Question

Hay una muy interesante rompecabezas para la secuencia de fibonacci

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

La respuesta es la secuencia de fibonacci: F(n) = F(n-1) + F(n-2). La explicación es que podría alcanzar el n-ésimo paso de la n-1º paso o n-2º paso.

Lo que no entiendo es por qué no es la respuesta F(n) = (F(n-1) + 1) + (F(n-2) + 2). Ya que, después de llegar a la n-1º paso que tengo que tomar de 1 paso para llegar a la n-ésimo paso y después de llegar a la n-2º paso tengo que tomar otro 2 pasos para llegar a la enésima paso.

Sé que puede ser ignorando algunas muy estúpido detalle, pero es mejor preguntar y ser llamado a un tonto una vez que siendo un tonto para siempre.

Answer 1

No estás contando el número de pasos involucrados, sólo el número de rutas. Para cada ruta que se presenta a $n-1$ pasos, no es exactamente una forma de terminar las escaleras (es decir, tomar el último paso). Con llegar a $n-2$, sólo hay una manera de terminar en ese punto, si usted insiste en tomar dos pasos a la vez. (Si usted toma un paso, usted está en lugar de la espalda para el primer escenario.) En ambos escenarios, no necesitamos añadir nada más: sólo hay que añadir el número de rutas que se llega a $n-1$ y el número que le a $n-2$.