Quantas são as sequências de
termos, todos pertencentes a
, que não possuem dois termos consecutivos iguais a 0 ?
Passo 1
Resumindo: queremos contar quantas sequências de comprimento
formadas pelos símbolos
não têm dois zeros consecutivos. O conteúdo é usar relações de recorrência para impedir o padrão “00”.
Passo 2
Definimos
como o número de sequências válidas de tamanho
. Para montar a recorrência, se a primeira posição for um símbolo não-zero (ou seja,
ou
), restam
posições livres sem restrição adicional, contribuindo com
.
Se, em vez disso, a primeira posição for , então a segunda não pode ser
; ela deve ser
ou
. Isso consome duas posições e deixa
posições que podem ser preenchidas de qualquer forma válida. Logo essa opção dá
.
Se, em vez disso, a primeira posição for
Passo 3
Combinando as duas situações, obtemos a recorrência
As condições iniciais são
Passo 4
Para resolver essa recorrência, consideramos o polinômio característico
cuja raízes são
Passo 5
Logo a solução geral é
Impondo
e
e resolvendo para
e
, encontra-se