<s>[INST] 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?
 [/INST] 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)$.
</s>