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:
  1. Do degrau subindo um degrau.
  2. 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.