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 pede o número de sequências de etapas em que Olavo faz 1 ou 2 pontos e, ao final, totaliza n pontos. Vamos chamar de a_n 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 n pontos, o último lance pode ter sido de 1 ponto (e antes disso já ter somado n-1 pontos) ou de 2 pontos (e antes disso já ter somado n-2 pontos). Assim obtemos a relação de recorrência
a_n = a_{n-1} + a_{n-2}.

Passo 3

Faltam as condições iniciais. Se n=0, só há a sequência vazia, logo
a_0 = 1.
Se n=1, só há uma etapa de 1 ponto, logo
a_1 = 1.

Passo 4

A recursão
a_n = a_{n-1} + a_{n-2},\quad a_0=1,\;a_1=1
define exatamente os números de Fibonacci deslocados. Concluímos que
a_n = F_{n+1},
onde \{F_k\} é a sequência de Fibonacci com F_0=0, F_1=1 e F_k=F_{k-1}+F_{k-2}.

Resposta

F_{n+1}, isto é, o (n+1)-ésimo número de Fibonacci.

Exercícios relacionados