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?

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.
