Uma escada possui
degraus,
, determine o número de maneiras distintas que se pode subir a escada se valem, simultaneamente, as seguintes restrições
não há a necessidade de passar por todos os degraus
não há a necessidade de passar por todos os degraus
Passo 1
O enunciado dá que:
- Há uma escada com
degraus, com . - Não é necessário passar por todos os degraus (ou seja, pode-se pular degraus).
O problema pede: - Determinar o número de maneiras distintas de subir da base até o topo (do degrau inicial até o degrau
) obedecendo a possibilidade de pular degraus.
Passo 2
Vamos formalizar o que conta como “uma maneira distinta”. Adoto a convenção natural:
- Começa-se no chão, que chamarei de degrau
, e termina-se no degrau . - Um movimento consiste em subir um número inteiro positivo de degraus (pelo menos 1). Podemos pular quantos degraus quisermos, desde que avancemos para um degrau de índice maior.
- Uma maneira distinta é uma sequência ordenada dos comprimentos dos saltos que somam
.
Vou chamar de
o número de maneiras de subir até o degrau
sob essas regras. A partir daqui resolvemos para
.
Passo 3
Verificando pequenos casos para intuir o problema:
- Para
: só há uma maneira: subir 1 degrau. Logo . - Para
: as maneiras possíveis (escrevendo comprimentos dos saltos) são e . Então .
Esses exemplos servem para checar depois se a fórmula obtida faz sentido.
Passo 4
Montando uma relação de recorrência: considere o primeiro salto ao subir uma escada de
degraus. Esse primeiro salto pode ter comprimento
, com
. Se o primeiro salto é
, resta subir
degraus; o número de maneiras para isso é
. Somando sobre todas as possibilidades do primeiro salto:
Para que a soma funcione de forma conveniente, definimos
(há exatamente uma maneira de não subir nada: a sequência vazia), o que é uma definição padrão para este tipo de contagem.
Passo 5
Manipulando a recorrência para simplificá-la. Escrevendo explicitamente:
Agora escrevendo a mesma fórmula para
:
Subtraindo a segunda da primeira obtemos:
Portanto
Passo 6
Resolver a recorrência linear simples
com a condição inicial
.
Aplicando a relação repetidamente:
Aplicando a relação repetidamente:
Podemos também provar por indução: hipótese de indução:
para todo
. Então
. A base
é verdadeira, logo a fórmula vale para todo
.
Passo 7
Interpretação combinatória alternativa (intuição extra, muito útil em prova): pense nos
degraus como
unidades em fila. Entre degrau
e
há
“fronteiras”. Para cada uma dessas
fronteiras podemos decidir se fazemos um “corte” ali (ou seja, terminamos um salto naquele ponto) ou não. Cada padrão de escolhas de cortes determina uma composição de
em partes positivas, ou equivalentemente uma sequência de saltos que soma
. Como há duas escolhas (cortar/não cortar) em cada uma das
fronteiras, o total é
. Esse argumento é uma bijeção direta e explica por que o resultado é potência de 2.