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

Passo 1

O enunciado pede: “Quantas são as sequências de n termos, todos pertencentes a \{0,1\}, que não possuem dois termos consecutivos iguais a 0?”\n
Informações relevantes dadas:
  • O comprimento da sequência é n.
  • Cada termo da sequência é ou 0 ou 1, isto é, pertencem ao conjunto \{0,1\}.
  • A condição proibitiva: não é permitido que apareçam dois zeros seguidos (não pode haver o padrão 00 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 n=1: as sequências possíveis são 0 e 1. Logo há 2 sequências.
  • Para n=2: as sequências possíveis são 11,\;10,\;01. A sequência 00 é proibida. Logo há 3 sequências.
Anotamos estes resultados iniciais, que servirão como condições iniciais mais adiante:
a_1=2,\qquad a_2=3,
onde a_n é o número de sequências válidas de comprimento n.

Passo 3

Definimos a quantidade que queremos contar. Seja a_n o número de sequências de comprimento n cujos termos são em \{0,1\} e que não contêm dois zeros consecutivos. Nosso objetivo é encontrar uma fórmula fechada (ou recursiva resolvida) para a_n.

Passo 4

Vamos encontrar uma relação entre a_n, a_{n-1} e a_{n-2} 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 n. Olhemos para o primeiro termo:
  • Se o primeiro termo for 1: então os n-1 termos restantes (posições 2 a n) podem ser qualquer sequência válida de comprimento n-1. Há, portanto, a_{n-1} sequências com primeiro termo 1.
  • Se o primeiro termo for 0: como não podemos ter dois zeros consecutivos, o segundo termo obrigatoriamente deve ser 1. Assim, os dois primeiros termos ficam fixos como 01, e os n-2 termos restantes (posições 3 a n) podem ser qualquer sequência válida de comprimento n-2. Há, portanto, a_{n-2} sequências com começo 01.
Esses dois casos são disjuntos e cobrem todas as possibilidades, logo somamos as contagens:
a_n = a_{n-1} + a_{n-2}.

Passo 5

Agora juntamos a relação recursiva com as condições iniciais. Temos a recorrência de segunda ordem
a_n = a_{n-1} + a_{n-2}\quad\text{para }n\ge 3,
com
a_1=2,\qquad a_2=3.
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 F_k, definida por
F_k = F_{k-1}+F_{k-2}\quad\text{para }k\ge 3,
com F_1=1 e F_2=1.
Compare a recorrência de a_n com a de F_k. Se tentarmos escrever a_n em termos de F, vejamos os primeiros valores de F:
F_1=1,\;F_2=1,\;F_3=2,\;F_4=3,\;F_5=5,\;\dots
Observamos que a_1=2=F_3 e a_2=3=F_4. Pela recorrência igual e pelos mesmos valores iniciais deslocados, concluímos que para todo n\ge1
a_n = F_{n+2}.
Isto é, a_n é o (n+2)-ésimo número de Fibonacci (com a convenção F_1=1,F_2=1).

Passo 7

Se quiseres uma fórmula explícita (fechada), podemos usar a fórmula de Binet para Fibonacci. Definimos
\varphi=\frac{1+\sqrt{5}}{2}\quad\text{e}\quad \psi=\frac{1-\sqrt{5}}{2}.
A fórmula de Binet diz que, para todo k,
F_k=\frac{\varphi^{k}-\psi^{k}}{\sqrt{5}}.
Portanto, aplicando isso ao nosso caso,
a_n = F_{n+2} = \frac{\varphi^{\,n+2}-\psi^{\,n+2}}{\sqrt{5}}.
Essa expressão dá diretamente o valor numérico de a_n sem recorrer à recorrência, embora para contar em prova normalmente a resposta F_{n+2} seja suficiente e elegante.

Passo 8

Pequeno exemplo para fixar:
  • Para n=3, pela fórmula a_3=F_5=5. Vamos listar para conferir: as sequências de comprimento 3 sem 00 são 111,110,101,011,010 — são 5. Confere!

Resposta

\displaystyle a_n=F_{n+2}=\frac{\varphi^{\,n+2}-\psi^{\,n+2}}{\sqrt{5}}

Exercícios relacionados