Finding recurrence relation that do not contain GOAL

Question

Find a recurrence relation and initial conditions for $c_n$, the number of sequences of length $n$ of upper case letters that do not contain GOAL.

Answer 1

I would start with $a_n$ as the number of sequences of length $n$ that DO contain GOAL. At the same time let us define $b_n$ as the number of sequences of length $n$ ending with GOA and NOT containing an instance of GOAL prior to that. Also let us assume that we have 26 letters.

Then $b_3=a_4=1$ and $b_n=26^{n-3}-a_{n-3}=c_{n-3}$ and then we have $$ a_{n+1}=a_n+b_n=a_n+c_{n-3}$$ Or put differently $a_{n+1}-a_n=c_{n-3}$. Now we can use this to describe $c_n=26^n-a_n$ where $26^n$ is the total number of possible sequences of length $n$. So $$ \begin{align} c_{n+1}-c_n&=26^{n+1}-a_{n+1}-(26^n-a_n)\\ &=26^{n+1}-26^n-(a_{n+1}-a_n)\\ &=26^{n+1}-26^n-c_{n-3} \end{align} $$ It now follows that $$ c_{n+1}=c_n+26^{n+1}-26^n-c_{n-3} $$ where $c_4=26^4-a_4=26^4-1$. Also $c_1$ and $c_2=26^2$ and $c_3=26^3$.