Quantas são as sequências de n termos, todos pertencentes a \{0,1,\{ que não possuem dois termos consecutivos iguais a 0 ? -

Passo 1

O problema pede: contar quantas sequências de n termos, com cada termo pertencendo ao conjunto \{0,1,2\}, não têm dois zeros consecutivos.
Informações dadas e o que se pede:
  • O alfabeto é \{0,1,2\} (três símbolos: um zero e dois símbolos não-zero).
  • Comprimento das sequências: n.
  • Restrição: a sequência não pode conter o padrão 00 (dois zeros consecutivos).
  • Objetivo: encontrar uma expressão (fórmula) para o número de tais sequências em função de n.

Passo 2

Vamos definir uma variável conveniente para contar: seja a_n o número de sequências de comprimento n que satisfazem a condição (sem dois zeros consecutivos). Quero agora decompor todas as sequências de comprimento n 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 n cujo último termo é não-zero (isto é, 1 ou 2). Para esse caso, o prefixo (os primeiros n-1 termos) pode ser qualquer sequência válida de comprimento n-1. Como há 2 escolhas para o último símbolo, o número de sequências desse tipo é 2\cdot a_{n-1}.
  • Sequências cujo último termo é 0. Nesse caso, para evitar dois zeros consecutivos, o penúltimo termo tem de ser não-zero (ou não existe, se n=1). Então podemos pensar: escolha os primeiros n-2 termos de qualquer sequência válida de comprimento n-2, escolha o termo n-1 como um não-zero ( 2 escolhas), e o último termo é fixo como 0. Assim o número de sequências desse tipo é 2\cdot a_{n-2} (válido para n\ge2; para n=1 trataremos separadamente com a condição inicial).
    Somando os dois tipos, obtemos a recorrência:
a_n = 2\,a_{n-1} + 2\,a_{n-2},\qquad \text{para } n\ge2.

Passo 4

Agora precisamos das condições iniciais (casos pequenos) para fixar a recorrência:
  • Para n=0 (sequência vazia) convém usar a_0=1 (há uma sequência vazia válida).
  • Para n=1: as sequências válidas são \{0,1,2\}, ou seja 3 possibilidades, então a_1=3.
    Verificação rápida: a recorrência para n=2 daria a_2=2a_1+2a_0=2\cdot3+2\cdot1=8. Lista explícita para n=2 confirma 8: 00 proibido; restam 3^2-1=8. Tudo coerente.

Passo 5

Resolvemos a recorrência linear de ordem 2 com coeficientes constantes. Escrevemos a equação característica associada:
r^2 - 2r - 2 = 0.
As raízes dessa equação são
r_{1,2}=\frac{2\pm\sqrt{4+8}}{2}=\frac{2\pm\sqrt{12}}{2}=1\pm\sqrt{3}.

Passo 6

A solução geral da recorrência tem a forma
a_n = A\,(1+\sqrt{3})^n + B\,(1-\sqrt{3})^n,
para constantes A e B que determinamos pelas condições iniciais a_0=1 e a_1=3.
Da condição a_0=1 obtemos
A+B=1.
Da condição a_1=3 obtemos
A(1+\sqrt{3})+B(1-\sqrt{3})=3.

Passo 7

Resolvendo o sistema para A e B:
a partir de A+B=1 temos B=1-A. Substituindo na segunda equação:
A(1+\sqrt{3})+(1-A)(1-\sqrt{3})=3.
Expandindo e simplificando:
A(1+\sqrt{3}) + 1-\sqrt{3} -A(1-\sqrt{3})=3
A\big[(1+\sqrt{3})-(1-\sqrt{3})\big] +1-\sqrt{3}=3
A(2\sqrt{3}) = 2+\sqrt{3}
A = \frac{2+\sqrt{3}}{2\sqrt{3}} = \frac{3+2\sqrt{3}}{6}.
Então
B=1-A = \frac{3-2\sqrt{3}}{6}.

Passo 8

Substituindo A e B na solução geral, obtemos a fórmula fechada para a_n:
a_n = \frac{3+2\sqrt{3}}{6}\,(1+\sqrt{3})^n + \frac{3-2\sqrt{3}}{6}\,(1-\sqrt{3})^n.
Essa expressão dá, para cada n\ge0, o número de sequências de comprimento n em \{0,1,2\} que não contêm dois zeros consecutivos. Alternativamente, podemos deixar a resposta como a recorrência com condições iniciais:
a_n = 2a_{n-1}+2a_{n-2},\quad a_0=1,\;a_1=3.

Resposta

a_n=\frac{3+2\sqrt{3}}{6}\,(1+\sqrt{3})^n+\frac{3-2\sqrt{3}}{6}\,(1-\sqrt{3})^n

Exercícios relacionados