Em um jogo, em cada etapa, Olavo pode fazer 1 ou 2 pontos. De quantos modos ele pode totalizar
pontos?
Passo 1
O enunciado pede o número de sequências de etapas em que Olavo faz 1 ou 2 pontos e, ao final, totaliza
pontos. Vamos chamar de
essa quantidade de modos. O conteúdo que usaremos é o de recorrência e identificação com a sequência de Fibonacci.
Passo 2
Para chegar a
pontos, o último lance pode ter sido de 1 ponto (e antes disso já ter somado
pontos) ou de 2 pontos (e antes disso já ter somado
pontos). Assim obtemos a relação de recorrência
Passo 3
Faltam as condições iniciais. Se
, só há a sequência vazia, logo
Se
, só há uma etapa de 1 ponto, logo
Passo 4
A recursão
define exatamente os números de Fibonacci deslocados. Concluímos que
onde
é a sequência de Fibonacci com
,
e
.