contar el número de palabras con longitud $n$ con $a,b,c$ que contienen un número impar de $a$ ' s.

Question

Encontrar las palabras con longitud $n$ $a,b,c$ que contienen un número impar de $a$ de uso ' s.

Mi intento: que $f_n$ la respuesta de la pregunta y $g_n$ la respuesta de la misma pregunta con número par de $a$'s.We:

$f_n=2f_{n-1}+g_{n-1}$

$g_n=2g_{n-1}+f_{n-1}$

Lo que conseguimos:

$g_n-f_n=g_{n-1}-f_{n-1}=\dots =g_1-f_1=1$

$f_n+g_n=3(f_{n-1}+g_{n-1})$

Así $2f_n+1=3(2f_{n-1}+1)$ y tenemos $f_n=3f_{n-1}+1$

Pero el libro le dio la respuesta $f_n=4f_{n-1}-3f_{n-2}$ así que necesito una respuesta que contiene la respuesta.

Answer 1

Esta combinatoria argumento podría ser satisfactoria:

Deje $S$ ser el conjunto de todas las cadenas que tienen número impar de $a$ s.

A continuación, el número de cadenas en $S$ que $a$ en el primer como el segundo lugar - $f_{n-2}$.

Otras cadenas en $S$ han $b$ o $c$ en el primer lugar o el segundo lugar:

Número de cadenas en $S$ que $b$ o $c$ en el primer lugar - $2f_{n-1}$.

Número de cadenas en $S$ que $b$ o $c$ en el segundo lugar - $2f_{n-1}$.

Número de cadenas en $S$ que $b$ o $c$ en ambos el primer y segundo lugar - $2\times2\times f_{n-2} = 4f_{n-2}$.

Mediante la inclusión-exclsion principio, el número de cadenas en $S$ que $b$ o $c$ en el primer o segundo lugar - $2f_{n-1}+2f_{n-1}-4f_{n-2} = 4(f_{n-1}-f_{n-2})$.

Así el número total de cadenas en $S$ - $f_n = 4(f_{n-1}-f_{n-2}) + f_{n-2} = 4f_{n-1}-3f_{n-2}$.

Answer 2

Tienes $f_n-3f_{n-1}=1$. También $f_{n-1}-3f_{n-2}=1$. Restar a estos, y te $f_n-4f_{n-1}+3f_{n-2}=0$.