How many $k$-letter words are there such that the letters A and B are not next to each other? I spent the better part of a long car ride today thinking about the following problem:

Consider an alphabet of $n$ letters. How many $k$-letter words of this alphabet are there such that two certain letters (say A and B) are not next to each other? A word may contain the same letter multiple times.

My thoughts: There are $n^k$ words with length $k$ over the alphabet. We need to find and subtract away the number of words where A and B are next to each other. I modeled any such word as one with the string AB or BA at an index $i$:
$$x_1x_2x_3\cdots x_{i-1}ABx_{i+2}\cdots x_k$$
The $x_j$ here are all letters of the alphabet. We can think of the above word as an $(i-1)$-letter word, followed by AB, followed by a $(k-i-2)$-letter word. Thus, there are $n^i \cdot n^{k-i-2} = n^{k-2}$ words where AB or BA is at an arbitrary index $i$. Summing over all $i$, we get that there are $(k-2)n^{k-2}$ words containing AB and $2(k-2)n^{k-2}$ words containing AB or BA. Our final expression for the number of $k$-letter words such that A and B are not adjacent is
$$n^k - 2(k-2)n^{k-2}$$
There’s an issue though. I’m over-counting words that contain AB or BA by a lot. I ran a simulation, and at $n=k=10$, for example, the correct value is $8441614754$, and my answer is $8400000000$. By this method, any word that contains AB or BA more than once is counted more than once. Is there any way I can modify this approach to yield the correct result? If not, how should I proceed?
 A: You can handle this with coupled recurrences.  Let $A(k)$ be the number of words without $AB$ or $BA$ that end in a character other than $A$ or $B$.  Let $B(k)$ be the number of words without $AB$ or $BA$ that end in $A$ or $B$.  You can add any character to an $A(k)$ word, but only $n-1$ characters to a $B(k)$ word, one of which leaves it as a $B(k+1)$ word.  The recurrences are
$$A(k+1)=(n-2)A(k)+(n-2)B(k)\\
B(k+1)=2A(k)+B(k)\\
A(0)=1\\
B(0)=0$$
For small $k$ you can make a spreadsheet to do these.  For large $k$ you can do the eigenvalue/eigenvector thing on the matrix $$\begin {pmatrix} n-2&n-2\\2&1 \end {pmatrix}$$
The leading eigenvalue is $\frac 12\left(\sqrt{n^2+2n-7}+n-1\right)\approx n$ when both $k$ and $n$ are large.  You want $A(k)+B(k)$
I made a spreadsheet for $n=10$, shown below.  In the line for $n=2$ the $98$ under $A+B$ shows there are $98$ two character strings that are not $AB$ or $BA$.  As there are $10^2=100$ unrestricted strings and we rule out $2$, this is correct.  The $18\ B$ strings have one of $9$ characters (not a $B$) then an $A$, or one of $9$ characters (not an $A$) then a $B$.

A: Consider the following automaton that accepts the strings not containing AB or BA,

From the DFA, using Chomsky-Schutzemberger method, we get,
$$q_0 = 1+xq_1+xq_2+(n-2)xq_0$$
$$q_1 = 1+xq_1+(n-2)xq_0$$
$$q_2 = 1+xq_2+(n-2)xq_0$$
(We omit $q_3$ and $q_4$ because it is a dead state)
On solving the above equations (i.e. substituting $q_1$ and $q_2$) we get the following expression for $q_0$,
$$q_0 = \frac{1+x}{1-(n-1)x-(n-2)x^{2}}$$
This is our generating function. The coefficient of $x^{k}$ gives the number of strings of length k not having AB or BA.
For example, for $n = k = 10$, Wolfram Alpha gives the following Taylor Series,

And as you can see, the coefficient of $x^{10}$ is equal to the answer you have provided.
A: This answer is based upon the Goulden-Jackson Cluster Method. We consider words of length $k\geq 0$ built from an alphabet $\mathcal{V}$ with $|\mathcal{V}|=n$ and the set $B=\{AB,BA\}$ of bad words, which are not allowed to be part of the words we are looking for.
We derive a generating function $A_n(z)$ with the coefficient of $z^k$ being  the number of wanted words of length $k$. According to the paper (p.7) the generating function $A_n(z)$  is
\begin{align*}
A_n(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}
\end{align*}
with $d=|\mathcal{V}|=n$, the size of the alphabet and $\mathcal{C}$ the weight-numerator with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[AB])+\text{weight}(\mathcal{C}[BA])
\end{align*}
We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C}[AB])&=-z^2-\text{weight}(\mathcal{C}[BA])z\\
\text{weight}(\mathcal{C}[BA])&=-z^2-\text{weight}(\mathcal{C}[AB])z\\
\end{align*}
and get
\begin{align*}
\text{weight}(\mathcal{C}[AB])=\text{weight}(\mathcal{C}[BA])=-\frac{z^2}{1+z}
\end{align*}
It follows
\begin{align*}
\color{blue}{A_n(z)}&=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-nz+2\frac{z^2}{1+z}}\\
&\,\,\color{blue}{=\frac{1+z}{1-(n-1)z-(n-2)z^2}}\tag{1}
\end{align*}

Denoting with $[z^k]$ the coefficient of $z^k$ of a series, we obtain from (1) the number of valid words of length $k$ as
\begin{align*}
\color{blue}{[z^k]}\color{blue}{A_n(z)}&=[z^k]\frac{1+z}{1-(n-1)z-(n-2)z^2}\\
&=[z^k]\sum_{j=0}^\infty z^j\left((n-1)+(n-2)z\right)^j(1+z)\\
&=\sum_{j=0}^k[z^{k-j}]\left((n-1)+(n-2)z\right)^{j}(1+z)\\
&=\sum_{j=0}^k[z^j]\left((n-1)+(n-2)z\right)^{k-j}(1+z)\\
&\,\,\color{blue}{=\sum_{j=0}^k\binom{k-j}{j}(n-2)^j(n-1)^{k-2j}}\\
&\qquad\qquad\color{blue}{+\sum_{j=1}^k\binom{k-j}{j-1}(n-2)^{j-1}(n-1)^{k-2j+1}}\tag{2}
\end{align*}

Plausibility check: Evaluating (2) at $n=k=10$ we obtain
\begin{align*}
[z^{10}]A_{10}(z)=8\ 441\ 614\ 754
\end{align*}
in accordance with OPs calculation.
