The question is
Let $T(n)$ be the number of length-$n$ strings of letters $a$, $b$ and $c$, that do not contain three consecutive $a$'s. Give a recurrence relation for $T(n)$ and justify it. (You do not have to solve it.)
How would I go about solving this problem. I found the initial conditions of
$n = 0, T(n) = 1$
$n = 1, T(n) = 3$
$n = 2, T(n) = 9$
$n = 3, T(n) = 26$
But I do not know what to do after that point.
Hint: Call such strings good. Let $p(n)$ be the number of good strings of length $n$ that end in a letter other than $a$. Let $q(n)$ be the number of good strings that end in a single $a$. Let $r(n)$ the number of good strings that end in two $a$'s. Note that $p(n)+q(n)+r(n)=T(n)$.
We have $$p(n+1)=2(p(n)+q(n)+r(n))=2T(n).\tag{$1$}$$ This is because we get a good word of length $n+1$ that doesn't end in $a$ by appending either $b$ or $c$ to any good word of length $n$. By similar reasoning, we have $$q(n+1)=p(n),\tag{$2$}$$ and $$r(n+1)=q(n).\tag{$3$}$$ Bump up the indices in Equation $(3)$ by $1$. We get $r(n+2)=q(n+1)=p(n)$.
Add the the right-hand sides and left-hand sides of the three displayed equations. We get $$T(n+1)=2T(n)+p(n)+q(n)=3T(n)-r(n).$$ But $r(n)=p(n-2)=2T(n-3)$. Thus $$T(n+1)=3T(n) -2T(n-3).$$
