Um esporte pouco conhecido é o de subir escadas. Encontre uma relação de recorrência para o número de maneiras
de se subir
degraus de uma escada, se a cada passo pode-se escolher subir um ou dois degraus. Se considerarmos a questão de iniciar com o pé direito ou esquerdo, como ficará a recorrência?
Passo 1
Vamos analisar o problema de contar de quantas maneiras podemos subir
degraus, podendo subir 1 ou 2 degraus de cada vez. Além disso, precisamos considerar se começamos com o pé direito ou esquerdo. Para resolver isso, vamos usar o conceito de relação de recorrência, que nos ajuda a expressar a quantidade de maneiras de subir os degraus de forma sequencial.
Passo 2
Primeiro, vamos entender como chegar a uma relação de recorrência sem considerar o pé com que começamos. Se estamos no degrau
, podemos ter chegado lá de duas maneiras:
- Do degrau
subindo um degrau. - Do degrau
subindo dois degraus.
Isso significa que o número de maneiras de chegar ao degrau
(
) é a soma das maneiras de chegar aos degraus
e
. Portanto, a relação de recorrência fica:
Passo 3
Agora, vamos considerar que começamos com o pé direito ou esquerdo. Isso adiciona uma variação nas maneiras de subir os degraus, já que a escolha do pé inicial influencia os passos subsequentes. Para cada uma das maneiras de subir os degraus sem considerar o pé, temos duas opções: começar com o pé direito ou com o esquerdo. Portanto, multiplicamos a relação anterior por 2 para levar em conta essa escolha inicial.
Assim, a nova relação de recorrência fica:
Resposta
A relação de recorrência para o número de maneiras de subir
degraus, considerando o pé inicial, é: