Uma escada possui
degraus,
, 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
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
degraus ( ), de quantas maneiras distintas é possível subir até o degrau se, a cada passo, pode-se subir exatamente degrau ou exatamente degraus? - Informação importante: os únicos movimentos permitidos são subir
degrau ou subir degraus; os passos podem ser combinados em qualquer ordem, contanto que a soma dos degraus subidos seja . - Objetivo final: apresentar o número de sequências distintas de movimentos (cada sequência é uma ordem de
s e s) que levam do degrau ao degrau .
Passo 2
Definição conveniente e raciocínio inicial (intuição): vamos chamar de
o número pedido — ou seja,
= número de maneiras de subir
degraus usando passos de
ou
.
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 e valores menores, que é fácil de usar.
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
Passo 3
Análise do último passo para obter uma relação (recorrência):
- Se a subida até o degrau
terminar com um último passo de degrau, então antes desse último passo a pessoa estava no degrau , e o número de maneiras de chegar até é . - Se a subida terminar com um último passo de
degraus, então antes desse último passo a pessoa estava no degrau , e o número de maneiras de chegar até é .
Esses dois casos são mutuamente exclusivos e cobrem todas as possibilidades. Logo, paravale
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
):
- Para
: só há uma forma: dar um passo de . Então
- Para
: há duas formas: dois passos de (sequência ) ou um passo de (sequência ). Então
Com a recorrência
para
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
Defina a sequência de Fibonacci usual por
Observa-se que a sequência
começa
e os Fibonacci são
. Portanto parece que
Prova por indução simples:
- Base: para
, e então ok. Para , e então ok. - Passo indutivo: suponha que para todos
vale . Então, usando a recorrência,
pois os Fibonacci satisfazem
. Assim a igualdade vale para
. Logo por indução
para todo
.
Esse é um resultado muito útil: o número de maneiras de subir degraus com passos
ou
é exatamente o
-ésimo número de Fibonacci (na convenção
).
Esse é um resultado muito útil: o número de maneiras de subir
Passo 6
Fórmula combinatória explícita (contagem por número de passos de
):
Outra maneira de visualizar e computar sem usar diretamente Fibonacci é contar por quantas vezes se usa o passo
.
Outra maneira de visualizar e computar
- Se usar exatamente
passos de , então eles somam degraus; os degraus restantes são cobertos por passos . O total de movimentos (passos) será . - Entre esses
movimentos, escolhem-se quais posições serão ocupadas pelos “2”. O número de escolhas é . - O valor de
pode variar de até .
Portanto
Essa soma é equivalente a
(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
pequeno.
Passo 7
Fórmula fechada (Fórmula de Binet) — útil para reconhecer crescimento assintótico:
A recorrência característica da relação tem polinômio característico
, cujas raízes são
A recorrência característica da relação
A solução geral da recorrência (com as constantes ajustadas pelos casos iniciais) dá a fórmula de Binet para Fibonacci. Como
, obtemos
Aqui
é a razão áurea (aprox.
) e
é o conjugado (aprox.
). Essa fórmula permite calcular
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):
-
: . -
: . -
: pelas regras: então . -
: então .
Esses valores seguemque é .