Recurrence for Number of Words of Length $r$ over $[n]$ with no three consecutive letters the same Question

Let $b_{n,r}$ be the number  words of length $r$ over $[n]=\{1,2,\dotsc, n\}$ with no three consecutive letters the same. Show that
  $$
b_{n,r}=(n-1)(b_{n,r-1}+b_{n,r-2})\quad (r>2)
$$
  with initial conditions $b_{n,1}=n$ and $b_{n, 2}=n^2$

This question is from Riordan's Introduction to Combinatorial Analysis.
Context
It is stated as a hint in the problem to consider those sequences in the question with a given element first (call these $b_{n,r}^\star$) and a given pair of elements first (call these $b_{n,r}^{\star\star}$) and derive a system of recurrences with $b_{n,r}$. 
Earlier I solved the corresponding problem (of no two consecutive letters the same) with correpsonding sequences $a_{n,r}$ and $a_{n,r}^\star$ (those sequences with a given element first) and derived the recurrences
$$
\begin{align}
a_{n,r}&=na_{n,r}^\star\\
a_{n,r}^\star&=(n-1)a_{n,r-1}^\star
\end{align}
$$
which imply that $a_{n,r}=n(n-1)^{r-1}$. This question is supposed to generalize this kind of method.
My Attempt
With notation discussed as before I was able to deduce that
$$
\begin{align}
b_{n,r}&=nb_{n,r}^\star\\
b_{n,r}^\star&=(n^2-1)b_{n,r-1}^\star
\end{align}
$$
since for the first position there are $n$ choices. Further, Once a given element is first, there are $n^2-1$ pairs that can follow. 
And here is where my doubts begin. For $b_{n,r}^{\star\star}$, there is no nice analysis can be done since beginning a sequence with $00$ and $01$ need two separate analyses. 
Also it seems that unlike in the previous problem the derived sequence $b_{n,r}^{\star\star}$ is not independent of choice of the given pair to start with.
Any help with an attempt using the context is preferred but other solutions are welcome as well.
 A: I would let $c_{n,r}$ be the number of words of length $r$ with not three consecutive letters the same and not ending in two letters the same and $d_{n,r}$ be the number of words of length $r$ with not three consecutive letters the same and ending in two letters the same.  We can then write coupled recurrences
$$c_{n,r}=(n-1)(c_{n-1,r}+d_{n-1,r})\\
d_{n,r}=c_{n-1,r}$$
because given a $c$ or a $d$ we can add a letter different from the last to get a $c$.  Given a $c$ we can add a matching letter to get a $d$.  Then
$$\begin {align}b_{n,r}&=c_{n,r}+d_{n,r}\\&=(n-1)(c_{n-1,r}+d_{n-1,r})+c_{n-1,r}\\
&=(n-1)c_{n-1,r}+(n-1)c_{n-2,r}+(n-1)(c_{n-2,r}+d_{n-2,r})\\
&=(n-1)c_{n-1,r}+(n-1)c_{n-2,r}+(n-1)(d_{n-1,r}+d_{n-2,r})\\
&=(n-1)(b_{n-1,r}+b_{n-2,r}) \end {align}$$
A: Using the notation given,
$$b^\star_{n,r}=(n-1)(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})\tag{1}$$
because a sequence that begins with exactly one copy of a particular letter  may be followed by a sequence beginning with either exactly 1 copy or 2 copies of the $n-1$ remaining letters.
Also
$$b^{\star\star}_{n,r}=(n-1)(b^\star_{n,r-2}+b^{\star\star}_{n,r-2})\, ,\tag{2}$$ 
using similar reasoning for sequences beginning with exactly two copies of a particular letter.
Now since there are $n$ possible first letters we have
$$b_{n,r}=n(b^\star_{n,r}+b^{\star\star}_{n,r})\tag{3}$$
total valid sequences. 
We can use $(1)$, $(2)$ and $(3)$ to give
$$\begin{align}b_{n,r}&=n(b^\star_{n,r}+b^{\star\star}_{n,r})\\[1ex] &=n((n-1)(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})+(n-1)(b^\star_{n,r-2}+b^{\star\star}_{n,r-2}))\\[1ex] &=(n-1)(n(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})+n(b^\star_{n,r-2}+b^{\star\star}_{n,r-2})\\[1ex] &=(n-1)(b_{n,r-1}+b_{n,r-2})\, .\tag*{$\blacksquare$}\end{align}$$
By the way: that is an incredible book in my opinion! I highly recommend the two chapters on rook polynomials.
A: Since other approaches are also welcome here is a technique called Goulden-Jackson Cluster Method which gives us a generating function from which we can derive the wanted recurrence relation.

We consider the words of length $r\geq 0$ built from an alphabet $$[n]=\{1,2,3,\ldots,n\}$$ and the set $B=\{111,222,333,\ldots,nnn\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function
  \begin{align*}
B_n(s)=\sum_{j=0}^\infty b_{n,j} s^j\qquad\qquad n\geq 1
\end{align*}
  with the coefficient of $s^r$ being  the number of searched words of length $r$.

According to the paper (p.7) the generating function $B_n(s)$  is
\begin{align*}
B_n(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=n$, the size of the alphabet and $\mathcal{C}$ the weight-numerator with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[111])+\text{weight}(\mathcal{C}[222])+\cdots+\text{weight}(\mathcal{C}[nnn])
\end{align*}
We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C}[kkk])&=-s^3-\text{weight}(\mathcal{C}[kkk])(s+s^2)\qquad\qquad 1\leq k\leq n\\
\end{align*}
and get
\begin{align*}
\text{weight}(\mathcal{C}[kkk])=-\frac{s^3}{1+s+s^2}\qquad\qquad 1\leq k\leq n\\
\end{align*}
from which
\begin{align*}
\text{weight}(\mathcal{C})&=\sum_{k=1}^n\text{weight}(\mathcal{C}[kkk])
=-\frac{ns^3}{1+s+s^2}\\
\end{align*}
follows.
$$ $$

We obtain from (1) for $n\geq 2$
  \begin{align*}
\color{blue}{B_n(s)}&=\sum_{j=0}^\infty b_{n,j}s^j\\
&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\
&=\left(1-ns+\frac{ns^3}{1+s+s^3}\right)^{-1}\\
&\color{blue}{=\frac{1+s+s^2}{1-(n-1)s-(n-1)s^2}}\tag{2}\\
&=1+ns+n^2s^2+n(n^2-1)s^3+n(n^3-2n+1)s^4+\cdots
\end{align*}
where the last line was calculated with the help of Wolfram Alpha.

$$ $$

We can derive the recurrence relation from (2) by multiplication with the denominator
  \begin{align*}
B_n(s)(1-(n-1)s-(n-1)s^2)&=1+s+s^2\tag{3}\\
\end{align*}
  from which by extraction of the coefficient of $s^r\,(r>2)$
  \begin{align*}
\color{blue}{b_{n,r}-(n-1)b_{n,r-1}-(n-1)b_{n,r-2}=0}
\end{align*}
  follows.

A: Using the Soup and Croutons diagram - an explanation of the GJ theory

This automaton produces strings with multiplicities. However, the multiplicities will be recorded in the generating function. For example, the cluster 11111 is generated with multiplicity 8 but will be exactly recorded as $1 + 3t +3t^2 + t^3$ in the "at least" generating function.


*

*1 1 1 1 1  has no t

*111 1 1 - at least one bad 111 (in first position)

*1 111 1 - at least one bad 111 (in the second position)

*1 1 111 - at least one bad 111 (in the third position)

*111 1 1 - at least two bad 111's (in first and second positions)

*111 11 - at least two bad 111's (in first and third positions)

*1 111 1 - at least two bad 111's (in second and third positions)

*111 1 1 - all three bad 111's 
$$C_k = k^3t + (k + k^2)tC_k$$ hence each $C_k$ has the generating function
$$ \frac {s^3t} {1 - st - s^2t}$$ 
By diagram we have $$S = 1 + nsS + nCS$$ so the generating function for S is
$$ \frac 1 { 1 - ns - n \frac {s^3t} {1 - st - s^2t}  }$$
By Goulden-Jackson PIE, we have $Exact(t) = AtLeast(t-1)$ and we are interested in $Exact(0)$ so we take $t = -1$ in previous and we obtain the expected - previously presented - result.
