Um esporte pouco conhecido é o de subir escadas. Encontre uma relação de recorrência para o número de maneiras a_n de se subir n 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 n 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 n, podemos ter chegado lá de duas maneiras:
  1. Do degrau n - 1 subindo um degrau.
  2. Do degrau subindo dois degraus.
Isso significa que o número de maneiras de chegar ao degrau n ( ) é a soma das maneiras de chegar aos degraus n - 1 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 n degraus, considerando o pé inicial, é:

Exercícios relacionados