Quantas são as sequências de
termos, todos pertencentes a
que não possuem dois termos consecutivos iguais a 0 ?
Passo 1
O enunciado pede: “Quantas são as sequências de
termos, todos pertencentes a
, que não possuem dois termos consecutivos iguais a
?”\n
Informações relevantes dadas:
Informações relevantes dadas:
- O comprimento da sequência é
. - Cada termo da sequência é ou
ou , isto é, pertencem ao conjunto . - A condição proibitiva: não é permitido que apareçam dois zeros seguidos (não pode haver o padrão
em nenhuma posição). - Objetivo: contar quantas sequências diferentes satisfazem essas condições.
Passo 2
Vamos observar os casos pequenos para ganhar intuição (sempre bom para ver o padrão). Conte, mentalmente, todas as sequências de comprimento pequeno sem dois zeros consecutivos.
- Para
: as sequências possíveis são e . Logo há sequências. - Para
: as sequências possíveis são . A sequência é proibida. Logo há sequências.
Anotamos estes resultados iniciais, que servirão como condições iniciais mais adiante:
onde
é o número de sequências válidas de comprimento
.
Passo 3
Definimos a quantidade que queremos contar. Seja
o número de sequências de comprimento
cujos termos são em
e que não contêm dois zeros consecutivos. Nosso objetivo é encontrar uma fórmula fechada (ou recursiva resolvida) para
.
Passo 4
Vamos encontrar uma relação entre
,
e
usando uma divisão por casos baseada no primeiro termo da sequência — técnica padrão e muito útil em contagem.
Considere todas as sequências válidas de comprimento
. Olhemos para o primeiro termo:
- Se o primeiro termo for
: então os termos restantes (posições a ) podem ser qualquer sequência válida de comprimento . Há, portanto, sequências com primeiro termo . - Se o primeiro termo for
: como não podemos ter dois zeros consecutivos, o segundo termo obrigatoriamente deve ser . Assim, os dois primeiros termos ficam fixos como , e os termos restantes (posições a ) podem ser qualquer sequência válida de comprimento . Há, portanto, sequências com começo .
Esses dois casos são disjuntos e cobrem todas as possibilidades, logo somamos as contagens:
Passo 5
Agora juntamos a relação recursiva com as condições iniciais. Temos a recorrência de segunda ordem
com
Essa recorrência é exatamente a mesma recorrência da sequência de Fibonacci, apenas com condições iniciais deslocadas. Vamos entender isso claramente.
Passo 6
Recordando a sequência de Fibonacci padrão
, definida por
com
e
.
Compare a recorrência de
com a de
. Se tentarmos escrever
em termos de
, vejamos os primeiros valores de
:
Observamos que
e
. Pela recorrência igual e pelos mesmos valores iniciais deslocados, concluímos que para todo
Isto é,
é o
-ésimo número de Fibonacci (com a convenção
).
Passo 7
Se quiseres uma fórmula explícita (fechada), podemos usar a fórmula de Binet para Fibonacci. Definimos
A fórmula de Binet diz que, para todo
,
Portanto, aplicando isso ao nosso caso,
Essa expressão dá diretamente o valor numérico de
sem recorrer à recorrência, embora para contar em prova normalmente a resposta
seja suficiente e elegante.
Passo 8
Pequeno exemplo para fixar:
- Para
, pela fórmula . Vamos listar para conferir: as sequências de comprimento sem são — são . Confere!