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
não há a necessidade de passar por todos os degraus

Passo 1

O enunciado dá que:
  • Há uma escada com n degraus, com n\ge 1.
  • 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 n) 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 0, e termina-se no degrau n.
  • 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 n.
Vou chamar de a(n) o número de maneiras de subir até o degrau n sob essas regras. A partir daqui resolvemos para a(n).

Passo 3

Verificando pequenos casos para intuir o problema:
  • Para n=1: só há uma maneira: subir 1 degrau. Logo a(1)=1.
  • Para n=2: as maneiras possíveis (escrevendo comprimentos dos saltos) são (1,1) e (2). Então a(2)=2.
    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 n degraus. Esse primeiro salto pode ter comprimento k, com 1\le k\le n. Se o primeiro salto é k, resta subir n-k degraus; o número de maneiras para isso é a(n-k). Somando sobre todas as possibilidades do primeiro salto:
a(n)=\sum_{k=1}^{n} a(n-k).
Para que a soma funcione de forma conveniente, definimos a(0)=1 (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:
a(n)=a(n-1)+a(n-2)+\cdots+a(0).
Agora escrevendo a mesma fórmula para a(n-1):
a(n-1)=a(n-2)+a(n-3)+\cdots+a(0).
Subtraindo a segunda da primeira obtemos:
a(n)-a(n-1)=a(n-1).
Portanto
a(n)=2\,a(n-1).

Passo 6

Resolver a recorrência linear simples a(n)=2\,a(n-1) com a condição inicial a(1)=1.
Aplicando a relação repetidamente:
a(1)=1,\qquad a(2)=2a(1)=2,\qquad a(3)=2a(2)=2^2,\\ \ldots,\\ a(n)=2^{n-1}.
Podemos também provar por indução: hipótese de indução: a(k)=2^{k-1} para todo k\le n-1. Então a(n)=2a(n-1)=2\cdot 2^{n-2}=2^{n-1}. A base a(1)=1=2^{0} é verdadeira, logo a fórmula vale para todo n\ge1.

Passo 7

Interpretação combinatória alternativa (intuição extra, muito útil em prova): pense nos n degraus como n unidades em fila. Entre degrau i e i+1 n-1 “fronteiras”. Para cada uma dessas n-1 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 n em partes positivas, ou equivalentemente uma sequência de saltos que soma n. Como há duas escolhas (cortar/não cortar) em cada uma das n-1 fronteiras, o total é 2^{n-1}. Esse argumento é uma bijeção direta e explica por que o resultado é potência de 2.

Resposta

2^{n-1}

Exercícios relacionados