Encontrar una relación de recurrencia en combinatoria

Question

Esta es la primera vez que trabajo con un problema de palabras con relaciones de recurrencia y estoy buscando si mis cálculos son correctos, o si hay otra manera de completar este problema

Encuentre una relación de recurrencia para el número de $n$ -secuencias de letras utilizando las letras $A, B, C$ de forma que $A$ que no está en la última posición de la secuencia siempre va seguido de un $B$ .

Digamos que hay $a_n$ tales secuencias.

Caso 1

(Empieza por C): El resto $n-1$ letras deben seguir la regla original, por lo que $a_{n-1}$ maneras.

Caso 2

(Empieza por B): El resto $n-1$ letras deben seguir la regla original, por lo que $a_{n-1}$ maneras.

Caso 3

(Empieza por A): La segunda letra debe ser B, y las restantes $n-2$ letras deben seguir la regla original, por lo que $a_{n-2}$ maneras.

Así que $a_n = 2a_{n-1} + a_{n-2}$ con condiciones iniciales $a_0 = 1$ , $a_1 = 3$ .

Answer 1

A mí me parece bien.

Para responder a la pregunta del OP en los comentarios: "¿podría alguien explicar por qué $a_0=1,a_1=3$ ":

En $n=0$ hay uno $0$ -secuencia de letras, la secuencia vacía $( )$ . Así que tenemos $a_0=1$ .

En $n=1$ hay $3$ secuencias de una letra que cumplen los criterios: $(A)$ , $(B)$ y $(C)$ por lo que tenemos $a_1=3$ .

Dos condiciones iniciales, $n=1$ y $n=0$ son necesarios porque nuestra relación de recurrencia implica dos términos anteriores. Si sólo utilizáramos $n=0$ como condición inicial, $a_{n-2}$ no siempre estaría bien definida (por ejemplo, si quisiéramos encontrar $a_1$ evaluando $a_1=2a_0+a_{-1}$ ).