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
em nenhum passo é permitido descer qualquer quantidade de degraus.

Passo 1

O enunciado dá uma escada com n degraus, com n\ge 1, e pede: determinar o número de maneiras distintas de subir a escada sabendo que, em nenhum passo, é permitido descer qualquer quantidade de degraus.
Informações relevantes dadas:
  • A escada tem n degraus.
  • Em cada movimento só é permitido subir (não descer) uma quantidade positiva de degraus.
  • A ordem dos movimentos importa (por exemplo, subir 2 depois 1 é diferente de subir 1 depois 2).
    O que se quer: o número total de sequências possíveis de movimentos (cada movimento é um inteiro positivo de degraus) cuja soma é exatamente n.

Passo 2

Interpretação precisa do problema (o que significa “maneira de subir”):
Uma “maneira” é uma sequência finita \big(k_1,k_2,\dots,k_m\big) com m\ge 1 tal que cada k_i é um inteiro positivo ( k_i\ge 1) e
k_1+k_2+\cdots+k_m = n.
Essas sequências são chamadas de composições do inteiro n. Vou explicar o que é uma composição e por que contar composições responde ao problema.

Passo 3

Definição e exemplo concreto de composição:
Uma composição de n é uma maneira de escrever n como soma ordenada de inteiros positivos. A ordem importa. Exemplos para ficar confortável:
  • Para n=1: as composições são (1). Total: 1.
  • Para n=2: composições: (2), (1,1). Total: 2.
  • Para n=3: composições: (3), (2,1), (1,2), (1,1,1). Total: 4.
  • Para n=4: composições: (4), (3,1), (1,3), (2,2), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1). Total: 8.
    Repare no padrão numérico 1,2,4,8,\dots que sugere potência de 2.

Passo 4

Prova combinatória direta (argumento dos espaços entre degraus):
Pense em n símbolos “1” alinhados: 1\;1\;1\;\dots\;1 (há n desses). Entre esses n uns há exatamente n-1 lacunas (ou “gaps”) onde podemos, opcionalmente, colocar uma quebra para separar blocos. Cada forma de agrupar os 1s em blocos contíguos determina uma composição: por exemplo, para n=5, se não colocarmos quebras em dois primeiros gaps, colocarmos quebra no terceiro e não no quarto, obtemos o agrupamento (3,2). Para cada um dos n-1 gaps há duas opções independentes: colocar quebra ou não colocar quebra. Logo o número total de escolhas de quebra é
2^{\,n-1}.
Cada escolha de subconjunto de gaps corresponde a exatamente uma composição (agrupamento) e cada composição é obtida por exatamente uma configuração de quebras — temos, portanto, uma bijeção. Assim o número de composições de n (isto é, o número de maneiras de subir a escada) é 2^{\,n-1}.

Passo 5

Prova alternativa por recorrência e indução (útil para a prova escrita na prova):
Defina a(n) como o número procurado. Se o primeiro movimento sobe k degraus com 1\le k\le n, o restante precisa cobrir n-k degraus, e há a(n-k) maneiras para isso. Portanto
a(n)=\sum_{k=1}^{n} a(n-k).
Mudando a indexação com j=n-k obtemos
a(n)=\sum_{j=0}^{n-1} a(j).
Tomando n-1 em vez de n temos
a(n-1)=\sum_{j=0}^{n-2} a(j).
Subtraindo as duas igualdades:
a(n)-a(n-1)=a(n-1)\quad\Rightarrow\quad a(n)=2\,a(n-1).
Com condição inicial a(1)=1 (só a sequência (1)), essa recorrência dá a(n)=2^{\,n-1} por indução simples: a(1)=2^{0} e se a(n-1)=2^{\,n-2} então a(n)=2\cdot 2^{\,n-2}=2^{\,n-1}.

Passo 6

Resumo final e observações:
  • O problema é equivalente a contar composições de n (somatórios ordenados de inteiros positivos que somam n).
  • Pelo argumento dos gaps (ou pela recorrência), o número de maneiras é \;2^{\,n-1}\; para todo n\ge 1.
    Isso bate com os exemplos numéricos: n=1\mapsto 1, n=2\mapsto 2, n=3\mapsto 4, n=4\mapsto 8, etc. Vai dar certo na prova — respira, tá dominado!

Resposta

2^{\,n-1}

Exercícios relacionados