Relación de recurrencia para subir una escalera

Question

Puedes subir una escalera dando un número impar de pasos a la vez. Por ejemplo, puedes subir una escalera de 10 peldaños dando cualquier número impar de pasos desde $1$ a $9$ a la vez. Creo que la relación de recurrencia para esto es $U_n = U_{n-1} + U_{n-3} + U_{n-5} + ...$ Pero el material del que estoy leyendo dice que la recurrencia se reduce a la de fibonacci. $U_n=U_{n-1}+U_{n-2}$ . No puedo entender esto.

Answer 1

Es cierto que la secuencia generada por esa relación de recurrencia es idéntica a la secuencia de Fibonacci (dados los casos base adecuados, por supuesto). Básicamente, se trata de las identidades que $$\sum_{k=0}^{n-1}F_{2k+1}=F_{2n}$$ y $$1+\sum_{k=1}^{n}F_{2k}=F_{2n+1}$$ que son bastante fáciles de demostrar por inducción.