Counting Strings There are 7 5 = 16,807 strings of length 5
formed from the 7 letters a, b, c, d, e, f, & g.   For example, one such string is ebdbg.
In how many of these 16,807 strings
are the letters b & d adjacent (appearing in either order  bd  or  db ) ?In other words, how many of these 16,807 strings contain either bd as a substring or contain db as a substring?
 A: For a nonnegative integer $n$, a string of length $n$ composed by letters $a,b,c,d,e,f,g$ containing $bd$ or $db$ as a substring is said to be $n$-suitable. Let $x_n$ denote the number of $n$-suitable strings.   Clearly, $x_0=0$, $x_1=0$, $x_2=2$, and $x_3=26$.
For $n>1$, it can be seen that
$$x_n=5x_{n-1}+10x_{n-2}+10x_{n-3}+\ldots+10x_1+2\cdot 7^{n-2}+2\cdot 7^{n-3}+\ldots +2\cdot 7^0\,.\tag{*}$$
To show this, look at the end of an $n$-suitable string $t_1t_2\ldots t_n$.  If $t_n\notin\{b,d\}$, then the string $t_1t_2\ldots t_{n-1}$ must be $(n-1)$-suitable.  There are $5$ choices for $t_n$, and so this gives $5x_{n-1}$ possible $n$-suitable strings with $t_n\notin\{b,d\}$.  
Now, suppose that $t_n\in\{b,d\}$.  Let $k$ be the smallest positive integer such that $$t_k=t_{k+1}=\ldots=t_{n}\,.$$
Clearly, $k>1$. If $t_{k-1}\in\{b,d\}\setminus\{t_n\}$, then $t_1t_2\ldots t_{k-2}$ can be arbitrary, so we have $2\cdot 7^{k-2}$ possibilities, recalling that there are two choices for $t_n$.
If $t_{k-1}\notin\{b,d\}$, then $t_1t_2\ldots t_{k-2}$ is a $(k-2)$-suitable string.  There are $5$ choices of $t_{k-1}$ and $2$ choices for $t_n$.  Thus, we have in total $10x_{k-2}$ possible varieties.  
From (*), we have
$$x_{n-1}=5x_{n-2}+10x_{n-3}+\ldots+10x_1+2\cdot 7^{n-3}+2\cdot 7^{n-4}+\ldots+2\cdot7^0$$
for $n>2$.  Subtracting the above result from (*), we get
$$x_n-x_{n-1}=5x_{n-1}+5x_{n-2}+2\cdot 7^{n-2}\,,$$
so
$$x_n-6x_{n-1}-5x_{n-2}=2\cdot7^{n-2}\,.$$
Solving the recurrence relation gives
$$x_n=7^n-\left(\frac{7-2\sqrt{14}}{14}\right)(3-\sqrt{14})^n-\left(\frac{7+2\sqrt{14}}{14}\right)(3+\sqrt{14})^n\,.$$
However, to get $x_5$, you do not need the general formula.  Just keep using the recurrence relation, you will get your desired answer.  In other words, you compute $x_4$ to get $$x_4=6x_3+5x_2+2\cdot 49=264\,.$$
Then,
$$x_5=6x_4+5x_3+2\cdot 343=2400\,.$$
A: This answer is based upon the Goulden-Jackson Cluster Method which is a convenient technique to derive a generating function for problems of this kind. 

We consider words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{a,b,c,d,e,f,g\}$$ and the set $B=\{bd,db\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being  the number of searched words of length $n$.The wanted number of words of length $5$ which do contain one of the bad words is consequently
  \begin{align*}
\color{blue}{7^5-[s^5]f(s)}
\end{align*}
  with $[s^n]$ denoting the coefficient of $f(s)$ of a series.

According to the paper (p.7) the generating function $f(s)$  is
\begin{align*}
f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}
\end{align*}
with $d=|\mathcal{V}|=7$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[bd])+\text{weight}(\mathcal{C}[db])
\end{align*}

We calculate according to the paper
  \begin{align*}
\text{weight}(\mathcal{C}[bd])&=-s^2-\text{weight}(\mathcal{C}[db])s\\
\text{weight}(\mathcal{C}[db])&=-s^2-\text{weight}(\mathcal{C}[bd])s\\
\end{align*}
  and get 
  \begin{align*}
\text{weight}(\mathcal{C}[bd])&=\text{weight}(\mathcal{C}[db])=\frac{-s^2}{1+s}\\
\text{weight}(\mathcal{C})&=\text{weight}(\mathcal{C}[bd])+\text{weight}(\mathcal{C}[db])\\
&=\frac{-2s^2}{1+s}
\end{align*}
We can now calculate $f(s)$
\begin{align*}
\color{blue}{f(s)}&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-7s+\frac{2s^2}{1+s}}\\
&=\frac{1+s}{1-6s-5s^2}\\
&=1+7s+47s^2+317s^3+2\,137s^4+\color{blue}{14\,407}s^5+97\,127s^6+\cdots\tag{1}
\end{align*}
  where the last line was done with some help of Wolfram Alpha.
We finally conclude from (1) the number of words containing at least one substring from  $\{bd,db\}$ is
  \begin{align*}
7^5-[x^5]f(s)=16\,807-14\,407=\color{blue}{2\,400}
\end{align*}

Hint: Some aspects of this approach are provided in the Add-on part of this answer.
