Uma escada possui n degraus, n \geq 1, determine o número de maneiras distintas que se pode subir a escada se valem, simultaneamente, as seguintes restrições
a cada passo pode-se optar por subir 1 ou 2 degraus

Passo 1

O que o problema pede e o que é dado:
  • Pergunta: para uma escada com n degraus ( n\ge 1), de quantas maneiras distintas é possível subir até o degrau n se, a cada passo, pode-se subir exatamente 1 degrau ou exatamente 2 degraus?
  • Informação importante: os únicos movimentos permitidos são subir 1 degrau ou subir 2 degraus; os passos podem ser combinados em qualquer ordem, contanto que a soma dos degraus subidos seja n.
  • Objetivo final: apresentar o número de sequências distintas de movimentos (cada sequência é uma ordem de 1s e 2s) que levam do degrau 0 ao degrau n.

Passo 2

Definição conveniente e raciocínio inicial (intuição): vamos chamar de a_n o número pedido — ou seja, a_n = número de maneiras de subir n degraus usando passos de 1 ou 2.
Explicando a ideia que vai guiar a solução (muito usada em provas): olhar o último passo que a pessoa faz. A decomposição pelo último movimento costuma gerar uma relação entre a_n e valores menores, que é fácil de usar.

Passo 3

Análise do último passo para obter uma relação (recorrência):
  • Se a subida até o degrau n terminar com um último passo de 1 degrau, então antes desse último passo a pessoa estava no degrau n-1, e o número de maneiras de chegar até n-1 é a_{n-1}.
  • Se a subida terminar com um último passo de 2 degraus, então antes desse último passo a pessoa estava no degrau n-2, e o número de maneiras de chegar até n-2 é a_{n-2}.
    Esses dois casos são mutuamente exclusivos e cobrem todas as possibilidades. Logo, para n\ge 3 vale
a_n = a_{n-1} + a_{n-2}.
Isto é chamado de recorrência de Fibonacci (ou uma recorrência linear de segunda ordem). Vou agora obter os casos iniciais para fixar completamente a solução.

Passo 4

Casos base (contagem direta para pequenos n):
  • Para n=1: só há uma forma: dar um passo de 1. Então
a_1 = 1.
  • Para n=2: há duas formas: dois passos de 1 (sequência 1,1) ou um passo de 2 (sequência 2). Então
a_2 = 2.
Com a recorrência a_n=a_{n-1}+a_{n-2} para n\ge 3 e esses dois valores iniciais, o problema fica totalmente determinado. Vou mostrar agora como isto conecta com os números de Fibonacci e dar fórmulas úteis.

Passo 5

Relação com a sequência de Fibonacci e prova por indução:
Defina a sequência de Fibonacci usual por
F_0=0,\qquad F_1=1,\qquad F_k=F_{k-1}+F_{k-2}\quad\text{para }k\ge 2.
Observa-se que a sequência a_n começa a_1=1,\;a_2=2,\;a_3=3,\;a_4=5,\ldots e os Fibonacci são F_0=0,\;F_1=1,\;F_2=1,\;F_3=2,\;F_4=3,\;F_5=5,\ldots. Portanto parece que
a_n = F_{n+1}.
Prova por indução simples:
  • Base: para n=1, a_1=1 e F_{1+1}=F_2=1 então ok. Para n=2, a_2=2 e F_{2+1}=F_3=2 então ok.
  • Passo indutivo: suponha que para todos k<n vale a_k=F_{k+1}. Então, usando a recorrência,
a_n = a_{n-1}+a_{n-2} = F_{n}+F_{n-1} = F_{n+1},
pois os Fibonacci satisfazem F_{n+1}=F_n+F_{n-1}. Assim a igualdade vale para n. Logo por indução a_n=F_{n+1} para todo n\ge 1.
Esse é um resultado muito útil: o número de maneiras de subir n degraus com passos 1 ou 2 é exatamente o (n+1)-ésimo número de Fibonacci (na convenção F_0=0,F_1=1).

Passo 6

Fórmula combinatória explícita (contagem por número de passos de 2):
Outra maneira de visualizar e computar a_n sem usar diretamente Fibonacci é contar por quantas vezes se usa o passo 2.
  • Se usar exatamente t passos de 2, então eles somam 2t degraus; os degraus restantes n-2t são cobertos por passos 1. O total de movimentos (passos) será (n-2t)+t = n-t.
  • Entre esses n-t movimentos, escolhem-se quais t posições serão ocupadas pelos “2”. O número de escolhas é \binom{n-t}{t}.
  • O valor de t pode variar de 0 até \lfloor n/2\rfloor.
    Portanto
a_n = \sum_{t=0}^{\lfloor n/2\rfloor} \binom{n-t}{t}.
Essa soma é equivalente a F_{n+1} (pode-se provar por indução que a soma satisfaz a mesma recorrência com os mesmos casos iniciais), mas às vezes é mais fácil de computar manualmente para n pequeno.

Passo 7

Fórmula fechada (Fórmula de Binet) — útil para reconhecer crescimento assintótico:
A recorrência característica da relação a_n=a_{n-1}+a_{n-2} tem polinômio característico r^2=r+1, cujas raízes são
\varphi = \frac{1+\sqrt{5}}{2}\quad\text{e}\quad \psi = \frac{1-\sqrt{5}}{2}.
A solução geral da recorrência (com as constantes ajustadas pelos casos iniciais) dá a fórmula de Binet para Fibonacci. Como a_n=F_{n+1}, obtemos
a_n = F_{n+1} = \frac{\varphi^{\,n+1}-\psi^{\,n+1}}{\sqrt{5}}.
Aqui \varphi é a razão áurea (aprox. 1{,}618\ldots) e \psi é o conjugado (aprox. -0{,}618\ldots). Essa fórmula permite calcular a_n diretamente (embora envolver radicais); para provas e para cálculo sem calculadora geralmente é melhor usar a recorrência ou a soma com binomiais.

Passo 8

Exemplos numéricos rápidos (para ganhar confiança):
  • n=1: a_1=1.
  • n=2: a_2=2.
  • n=3: pelas regras: (1,1,1),(1,2),(2,1) então a_3=3.
  • n=4: (1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2) então a_4=5.
    Esses valores seguem a_n=1,2,3,5,8,\ldots que é F_{n+1}.

Resposta

a_1=1,\quad a_2=2,\quad a_n=a_{n-1}+a_{n-2}\\ \text{para }n\ge 3
a_n = \displaystyle\sum_{t=0}^{\lfloor n/2\rfloor} \binom{n-t}{t}
a_n = F_{n+1} = \displaystyle\frac{\varphi^{\,n+1}-\psi^{\,n+1}}{\sqrt{5}},\\ \text{onde }\varphi=\dfrac{1+\sqrt{5}}{2},\\ \psi=\dfrac{1-\sqrt{5}}{2}

Exercícios relacionados