Possivelmente, esse problema pode ser resolvido usando Análise Combinatória (talvez outra pessoa possa apresentar essa solução). Mas note que a solução abaixo é simples e muito intuitiva.
Para ir para o degrau 1 existe apenas uma possibilidade. Logo, o número de possibilidades é igual a 1.
Para ir para o degrau 2 existem duas possibilidades: dando 1 salto de tamanho 2 do degrau zero ou dando 1 salto de tamanho 1 do degrau 1. Logo o número de possibilidades é igual 1+1=2.
Para ir para o degrau 3 existem duas possibilidades: dando 1 salto de tamanho 1 do degrau 2 ou dando um salto de tamanho 2 do degrau 1. Logo o número de possibilidades é igual 2+1=3.
Ou seja, para qualquer degrau \(n\gt 1\), existem duas possibilidades ou vindo do degrau anterior, onde foram possíveis \(x_{n-1}\) formas diferentes, ou do degrau anterior, onde foram possíveis \(x_{n-2}\) formas diferentes. Logo, para se chegar ao degrau são necessárias \(x_{n}=x_{n-1}+x_{n-2}\) soluções possíveis que é justamente a sequência de Fibonacci.