Esta es la solución más válida que te podemos dar, pero estúdiala pausadamente y valora si se puede adaptar a tu trabajo.
Solución:
Sea $b_n$ el número de cadenas ternarias de $n$ dígitos que comienzan con $0$ y no contienen ni $00$ ni $11$. Sea $c_n,d_n$ igual excepto que comience con $1$ o $2$ respectivamente. Sea $$t_n=b_n+c_n+d_n$$ el número total de cadenas ternarias de $n$ dígitos que no contienen ni $00$ ni $11$. Lo que quieres es $$a_n=3^n-t_n .$$ Para encontrar una recurrencia para $b_n$ observa que un ternario de $n$ dígitos string que comienza con $0$ y no contiene ni $00$ ni $11$ es
- $0$, seguido de un dígito $(n-1)$ string que comienza con $1$ y no contiene ni $00$ ni $11$; o
- $0$, seguido de un dígito $(n-1)$ string que comienza con $2$ y no contiene ni $00$ ni $11$.
Por lo tanto $$b_n=c_n-1+d_n-1 ;$$ argumentos similares dan $$c_n=b_n-1+d_n-1$$ y $$d_n=b_ n-1+c_n-1+d_n-1=t_n-1 .$$ Sumar todos estos da $$t_n=2t_n-1+d_n- 1$$ y entonces $$t_n=2t_n-1+t_n-2 .$$ Escribiendo en términos de $a_n$, tenemos $$3^n-a_n=2(3^n -1-a_n-1)+(3^n-2-a_n-2)$$ que se simplifica a $$a_n=2a_n-1+a_n-2 +2veces3^n-2 .$$
Te invitamos a asentar nuestra publicación mostrando un comentario y dejando una puntuación te damos la bienvenida.