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: