Encontre uma recorrência para a_n, o número de sequências de n letras dentre a, b, c ou d, que não têm letras a vizinhas.

Passo 1

Então, a gente precisa encontrar uma recorrência para a_n, que representa o número de sequências de n letras escolhidas entre a, b, c ou d, garantindo que não tenham letras a 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:
  1. Uma letra diferente de a (ou seja, b, c, ou d).
  2. A letra a.

Passo 3

Caso 1: Se o último caractere for b, c ou d, então as primeiras n - 1 letras podem formar qualquer sequência válida de tamanho n - 1 (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 a, precisamos garantir que o caractere antes dele não seja a (para evitar duas a juntas). Assim, as primeiras letras devem formar uma sequência válida de tamanho , e o penúltimo caractere pode ser b, c ou d (3 opções). Então, esse caso contribui com:

Passo 5

Somando os dois casos, a recorrência que relaciona a_n com os termos anteriores fica:

Resposta

A recorrência para a_n é:

Exercícios relacionados