Em um jogo, em cada etapa, Olavo pode fazer 1 ou 2 pontos. De quantos modos ele pode totalizar
pontos?
Passo 1
O enunciado pergunta em quantos modos Olavo pode atingir exatamente
pontos se, em cada etapa, ele faz ou 1 ponto ou 2 pontos.
O conteúdo aqui é contagem de composições de um inteiro usando partes de tamanho 1 e 2, que leva a uma recorrência tipo Fibonacci.
O conteúdo aqui é contagem de composições de um inteiro usando partes de tamanho 1 e 2, que leva a uma recorrência tipo Fibonacci.
Passo 2
Seja
o número de modos de totalizar
pontos. Para chegar a
pontos, na última jogada ele ou fez 1 ponto (e vinha de
pontos) ou fez 2 pontos (e vinha de
pontos). Logo, para
vale
Passo 3
Faltam as condições iniciais.
Para só há uma sequência possível:
, logo
.
Para há duas sequências:
e
, logo
.
Para
Para
Passo 4
A recorrência
é a mesma dos números de Fibonacci deslocados. De fato, se
,
e
, então