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

Passo 1

Resumindo: queremos contar quantas sequências de comprimento n formadas pelos símbolos \{0,1,2\} 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 f(n) como o número de sequências válidas de tamanho n. Para montar a recorrência, se a primeira posição for um símbolo não-zero (ou seja, 1 ou 2), restam n-1 posições livres sem restrição adicional, contribuindo com 2\,f(n-1).
Se, em vez disso, a primeira posição for 0, então a segunda não pode ser 0; ela deve ser 1 ou 2. Isso consome duas posições e deixa n-2 posições que podem ser preenchidas de qualquer forma válida. Logo essa opção dá 2\,f(n-2).

Passo 3

Combinando as duas situações, obtemos a recorrência
f(n)=2\,f(n-1)+2\,f(n-2).
As condições iniciais são
f(0)=1\quad(\text{sequência vazia}), \qquad f(1)=3\quad(\{0,1,2\}).ê

Passo 4

Para resolver essa recorrência, consideramos o polinômio característico
x^2-2x-2=0,
cuja raízes são
r_{1}=1+\sqrt{3}, \qquad r_{2}=1-\sqrt{3}.

Passo 5

Logo a solução geral é
f(n)=A\,(1+\sqrt{3})^n + B\,(1-\sqrt{3})^n.
Impondo f(0)=1 e f(1)=3 e resolvendo para A e B, encontra-se
A=\frac{1}{2}+\frac{1}{\sqrt{3}}, \qquad B=\frac{1}{2}-\frac{1}{\sqrt{3}}.

Resposta

\boxed{f(n) =\Bigl(\tfrac12+\tfrac{1}{\sqrt{3}}\Bigr)\,(1+\sqrt{3})^n +\Bigl(\tfrac12-\tfrac{1}{\sqrt{3}}\Bigr)\,(1-\sqrt{3})^n.}

Exercícios relacionados