Number of strings of length $n$ with no consecutive $y$'s Suppose we have a set $S$ such that $\lvert S\rvert=k+1$. Fix an element $y$ in $S$. We want to find the recurrence relation on the number of $S$-strings of length $n$ that don't have two consecutive $y$'s, namely $yy$. Use $f(n)$ to denote the answer.
I already find some initial conditions: for $f(1)$, that is the number of $S$-strings of length $1$ without two consecutive $y$'s, which is obviously $f(1)=k+1$; For $f(2)$, there is only one string that has two consecutive $y$'s, which is $yy$, so $f(2)=(k+1)^2-1$; For $f(3)$, If we place the two consecutive $y$'s at the first and the second positions, there are $k+1$ strings and $yyy$ are among the $k+1$ strings; If we place $yy$ at the second and the third positions, there are another $k+1$ strings and $yyy$ are also among these $k+1$ strings. So we conclude $f(3)=(k+1)^3-(2k+1)$.
Yet I have no idea what the general case is like. Any help please?
 A: Let $g(n)$ be the number of good $S$-strings of length $n$ ending in $y$ and $h(n)$ the other case. We have $f(n)=g(n)+h(n)$. The only way to get a good $S$-string ending in $y$ is with a good $S$-string not ending in $y$, and putting a $y$ on the end. So $g(n)=h(n-1)$. Additionally, $h(n)=kg(n-1)+kh(n-1)$ for similar reasons. Hence $h(n)=kh(n-1)+kh(n-2)$ and $h(0)=0, h(1)=k$. Recall $f(n)=h(n)+h(n-1)=h(n+1)/k$, so that $f(n)=kf(n-1)+kf(n-2)$ and $f(0)=1, f(1)=k+1$.
A: The empty string does not contain two consecutive $y$s, so $f(0) = 1$.  None of the $k + 1$ strings of length $1$ contain two consecutive $y$s, so $f(1) = k + 1$.  Every string of length $2$ is admissible except $yy$, so $f(2) = (k + 1)^2 - 1 = k^2 + 2k + 1 - 1 = k^2 + 2k$.
An admissible string of length $n \ge 2$ must either begin with an element $x \in S$ other than $y$ or must begin $yx$, where $x \in S$ and $x \neq y$.  If a string begins with $x \in S$, where $x \neq y$, it can be extended to an admissible string of length $n$ by appending an admissible string of length $n - 1$ to the end of the string $x$. There are $k$ ways to choose $x \in S$ such that $x \neq y$ and $f(n - 1)$ admissible strings of length $n - 1$, so there are $kf(n - 1)$ such words.  A string that begins with $yx$, where $x \in S$ and $x \neq y$, can be extended to an admissible string of length $n$ by appending an admissible string of length $n - 2$ to the end of the string $yx$.  There are $k$ ways to choose $x$ and $f(n - 2)$ admissible strings of length $n - 2$. Hence, there are $kf(n - 2)$ such strings.  Thus, we have
\begin{align*}
f(0) & = 1\\
f(1) & = k + 1\\
f(n) & = kf(n - 1) + kf(n - 2), n \ge 2
\end{align*}
Notice that we obtain
\begin{align*}
f(2) & = kf(1) + kf(0)\\
     & = k(k + 1) + k \cdot 1\\
     & = k^2 + k + k\\
     & = k^2 + 2k
\end{align*}
which agrees with your calculation $f(2) = (k + 1)^2 - 1$, and
\begin{align*}
f(3) & = kf(2) + kf(1)\\
     & = k(k^2 + 2k) + k(k + 1)\\
     & = k^3 + 2k^2 + k^2 + k\\
     & = k^3 + 3k^2 + k
\end{align*}
which agrees with your calculation $f(3) = (k + 1)^3 - (2k + 1)$.
A: This answer is based upon the Goulden-Jackson Cluster Method. We consider the set of words of length $n\geq 0$ built from an alphabet $S$ of $k+1$ letters with $y\in S$ and the set $B=\{yy\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $F(z)$ with the coefficient of $z^n$ being  the number of wanted words of length $n$.
According to the paper (p.7) the generating function $F(z)$  is
\begin{align*}
F(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=|\mathcal{S}|=k+1$, the size of the alphabet and $\mathcal{C}$ is the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[yy])\tag{2}
\end{align*}
We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C}[yy])&=-z^2-z\cdot\text{weight}(\mathcal{C}[yy])\tag{3}\\
\text{weight}(\mathcal{C}[yy])&=-\frac{z^2}{1+z}\\
\end{align*}
so  that
\begin{align*}
\text{weight}(\mathcal{C})=-\frac{z^2}{1+z}
\end{align*}
The additional term on the right-hand side of (3) takes account of the overlapping of $\color{blue}{y}y$ with $y\color{blue}{y}$.

We obtain according to (1) and (3)
\begin{align*}
\color{blue}{F(z)}&=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-(k+1)z+\frac{z^2}{1+z}}\\
&\; \color{blue}{=\frac{1+z}{1-kz(1+z)}}\tag{4}\\
\end{align*}

We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series.

We calculate from (4) $f(n)$ as
\begin{align*}
\color{blue}{f(n)}&=[z^n]F(z)=[z^n]\frac{1+z}{1-kz(1+z)}\\
&=[z^n](1+z)\sum_{q=0}^{\infty}k^qz^q(1+z)^q\tag{5.1}\\
&=\left([z^n]+[z^{n-1}]\right)\sum_{q=0}^{\infty}k^qz^q(1+z)^q\tag{5.2}\\
&=\sum_{q=0}^n[z^{n-q}]k^q(1+z)^q+\sum_{q=0}^{n-1}[z^{n-1-q}]k^q(1+z)^q\tag{5.3}\\
&=\sum_{q=0}^nk^q\binom{q}{n-q}+\sum_{q=0}^{n-1}k^q\binom{q}{n-1-q}\tag{5.4}\\
&\,\,\color{blue}{=k^n+\sum_{q=0}^{n-1}\left(\binom{q}{n-q}k+\binom{q}{n-1-q}\right)k^{n-1-q}}\tag{5.5}\\
\end{align*}

Comment:

*

*In (5.1) we use the geometric series expansion.


*In (5.2) we apply the rule $[z^{p-q}]F(z)=[z^p]z^qF(z)$.


*In (5.3) we apply the rule again and restrict the upper limits of the sum since other terms do not contribute.


*In (5.4) we select the coefficient of $[z^{n-q}]$ and $[z^{n-q-1}]$.


*In (5.5) we separate the term $k^n$ and merge the sums.
We verify (5.5) for small values $k=2,3$
\begin{align*}
\color{blue}{f(2)}&=k^2+\sum_{q=0}^1\left(\binom{q}{2-q}+\binom{q}{1-q}\right)k^q\\
&=k^2+\left(\binom{1}{1}+\binom{1}{0}\right)k\\
&\,\,\color{blue}{=k^2+2k}\\
\color{blue}{f(3)}&=k^3+\sum_{q=0}^2\left(\binom{q}{3-q}+\binom{q}{2-q}\right)k^q\\
&=k^3+\binom{1}{1}k+\left(\binom{2}{1}+\binom{2}{0}\right)k^2\\
&\,\,\color{blue}{=k^3+3k^2+k}
\end{align*}
in accordance with the result from other answers.
