Em um jogo, em cada etapa, Olavo pode fazer 1 ou 2 pontos. De quantos modos ele pode totalizar n pontos?

Passo 1

O enunciado pergunta em quantos modos Olavo pode atingir exatamente n 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.

Passo 2

Seja a_n o número de modos de totalizar n pontos. Para chegar a n pontos, na última jogada ele ou fez 1 ponto (e vinha de n-1 pontos) ou fez 2 pontos (e vinha de n-2 pontos). Logo, para n\ge3 vale
a_n = a_{n-1} + a_{n-2}.

Passo 3

Faltam as condições iniciais.
Para n=1 só há uma sequência possível: [1], logo a_1=1.
Para n=2 há duas sequências: [1,1] e [2], logo a_2=2.

Passo 4

A recorrência
a_n = a_{n-1} + a_{n-2},\quad a_1=1,\;a_2=2
é a mesma dos números de Fibonacci deslocados. De fato, se F_1=1, F_2=1 e F_{k}=F_{k-1}+F_{k-2}, então
a_n = F_{n+1}.

Resposta

a_n = F_{n+1}, onde \{F_k\} é a sequência de Fibonacci com F_1=1 e F_2=1.

Exercícios relacionados