Encontre uma recorrência para
, o número de sequências de
letras dentre
ou
, que não têm letras
vizinhas.
Passo 1
Então, a gente precisa encontrar uma recorrência para
, que representa o número de sequências de
letras escolhidas entre
ou
, garantindo que não tenham letras
vizinhas. Para resolver isso, vamos usar conceitos de recursão e contar as possibilidades passo a passo.
Passo 2
Vamos analisar como a sequência pode terminar. O último caractere da sequência pode ser:
- Uma letra diferente de
(ou seja, , , ou ). - A letra
.
Passo 3
Caso 1: Se o último caractere for
,
ou
, então as primeiras
letras podem formar qualquer sequência válida de tamanho
(já que não estamos impondo restrições adicionais). Como temos 3 opções para o último caractere, isso dá um total de:
Passo 4
Caso 2: Se o último caractere for
, precisamos garantir que o caractere antes dele não seja
(para evitar duas
juntas). Assim, as primeiras
letras devem formar uma sequência válida de tamanho
, e o penúltimo caractere pode ser
,
ou
(3 opções). Então, esse caso contribui com:
Passo 5
Somando os dois casos, a recorrência que relaciona
com os termos anteriores fica:
Resposta
A recorrência para
é: