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, é:
Exercícios relacionados
Reveja a definição de Números de Bell
no Corolário 3.1.8. Mostre a seguinte recorrência:
Dica: note que o número de Bell
é o número de possíveis relações de equivalência um conjunto
, sendo
. Fixe então um elemento de
e denote por
o número de elementos da classe de equivalência que contém esse elemento.
Obtenha uma relação de recorrência para o problema das Torres de Hanói apresentado no Exercício 1.1.20.
Considere o conjunto das sequências de tamanho
tais que cada entrada pertence a
e entradas vizinhas sempre diferem por 1 em módulo. Descreva um sistema de equações de recorrência para resolver este problema.
Encontre uma recorrência para
, o número de sequências de
letras dentre
ou
, que não têm letras
vizinhas.