Quantas são as sequências de
termos, todos pertencentes a
que não possuem dois termos consecutivos iguais a 0 ? -
Passo 1
O problema pede: contar quantas sequências de
termos, com cada termo pertencendo ao conjunto
, não têm dois zeros consecutivos.
Informações dadas e o que se pede:
Informações dadas e o que se pede:
- O alfabeto é
(três símbolos: um zero e dois símbolos não-zero). - Comprimento das sequências:
. - Restrição: a sequência não pode conter o padrão
(dois zeros consecutivos). - Objetivo: encontrar uma expressão (fórmula) para o número de tais sequências em função de
.
Passo 2
Vamos definir uma variável conveniente para contar: seja
o número de sequências de comprimento
que satisfazem a condição (sem dois zeros consecutivos). Quero agora decompor todas as sequências de comprimento
em dois tipos, olhando para o último termo — essa é uma técnica padrão de contagem por casos que gera recorrências.
Passo 3
Partição por último termo:
- Sequências de comprimento
cujo último termo é não-zero (isto é, ou ). Para esse caso, o prefixo (os primeiros termos) pode ser qualquer sequência válida de comprimento . Como há escolhas para o último símbolo, o número de sequências desse tipo é . - Sequências cujo último termo é
. Nesse caso, para evitar dois zeros consecutivos, o penúltimo termo tem de ser não-zero (ou não existe, se ). Então podemos pensar: escolha os primeiros termos de qualquer sequência válida de comprimento , escolha o termo como um não-zero ( escolhas), e o último termo é fixo como . Assim o número de sequências desse tipo é (válido para ; para trataremos separadamente com a condição inicial).
Somando os dois tipos, obtemos a recorrência:
Passo 4
Agora precisamos das condições iniciais (casos pequenos) para fixar a recorrência:
- Para
(sequência vazia) convém usar (há uma sequência vazia válida). - Para
: as sequências válidas são , ou seja possibilidades, então .
Verificação rápida: a recorrência paradaria . Lista explícita para confirma 8: proibido; restam . Tudo coerente.
Passo 5
Resolvemos a recorrência linear de ordem 2 com coeficientes constantes. Escrevemos a equação característica associada:
As raízes dessa equação são
Passo 6
A solução geral da recorrência tem a forma
para constantes
e
que determinamos pelas condições iniciais
e
.
Da condição obtemos
Da condição
Da condição
obtemos
Passo 7
Resolvendo o sistema para
e
:
a partir de temos
. Substituindo na segunda equação:
a partir de
Expandindo e simplificando:
Então
Passo 8
Substituindo
e
na solução geral, obtemos a fórmula fechada para
:
Essa expressão dá, para cada
, o número de sequências de comprimento
em
que não contêm dois zeros consecutivos. Alternativamente, podemos deixar a resposta como a recorrência com condições iniciais: