Uma string que contém apenas
e 2 s é chamada de string ternária.
Encontre uma relação de recorrência para o número de strings ternárias que contenham dois 0s consecutivos.
Encontre uma relação de recorrência para o número de strings ternárias que contenham dois 0s consecutivos.
Passo 1
Beleza, vamos lá! O enunciado fala sobre strings ternárias, que são sequências feitas só com os números 0, 1 e 2. Nosso objetivo é encontrar uma relação de recorrência para contar quantas dessas strings têm dois 0s consecutivos. Para isso, vamos precisar entender um pouco sobre relação de recorrência e como ela se aplica a esse problema.
Passo 2
Primeiro, vamos definir o que queremos contar. Vamos chamar de $ R(n) $ o número de strings ternárias de comprimento $ n $ que contêm pelo menos dois 0s seguidos. Nosso objetivo é expressar $ R(n) $ em termos de valores anteriores, como $ R(n-1) $, $ R(n-2) $, etc.
Passo 3
Vamos pensar em como construir uma string ternária válida de comprimento $ n $. A última posição dessa string pode ser 0, 1 ou 2. Vamos analisar cada caso:
-
Último caractere é 1 ou 2: Se o último caractere for 1 ou 2, os $ n-1 $ primeiros caracteres podem ser qualquer string ternária de comprimento $ n-1 $ que já contenha dois 0s consecutivos. Isso nos dá $ 2 \times R(n-1) $ possibilidades.
-
Último caractere é 0: Aqui precisamos ter cuidado. Para que a string toda tenha dois 0s consecutivos, os $ n-1 $ primeiros caracteres devem terminar com um 0. Ou seja, a penúltima posição também deve ser 0. Então, os primeiros $ n-2 $ caracteres podem ser qualquer string ternária de comprimento $ n-2 $ que já contenha dois 0s consecutivos, e adicionamos dois 0s no final. Isso nos dá $ R(n-2) $ possibilidades.
Passo 4
Agora, juntando os dois casos, temos que o total de strings ternárias de comprimento $ n $ com pelo menos dois 0s consecutivos é a soma das possibilidades dos dois casos:
Resposta
A relação de recorrência para o número de strings ternárias de comprimento $ n $ que contêm dois 0s consecutivos é: