A letter sequence problem If I have an $8$ letter string of the letters $C$ and $N$, how many ways can I arrange the letters so that no two N's are adjacent to each other?
 A: Here we derive a recurrence relation. We consider words of length $n$ built from an alphabet $\{C,N\}$ and denote the number of valid words with $a_n$.
We obtain a recurrence relation for $a_{n+1}$ by partitioning valid words of length $n+1$ into two disjoint sets.

*

*Termination with $C$: A word of length $n+1$ may end with the letter $C$. In this case we have $a_n$ possibilities to fill the left-most $n$ positions with valid words.

*Termination with $N$: If on the other hand the word terminates with $N$ it terminates in fact with $CN$, since $NN$ is not admissible. We have therefore $a_{n-1}$ possibilities to fill the $n-1$ left-most positions with valid words of length $n-1$.
We obtain the recurrence relation
\begin{align*}
\color{blue}{a_{n+1}=a_n+a_{n-1}\qquad\qquad n\geq 1}
\end{align*}
It is easy to determine the initial conditions, since the valid words of length $n=1$ are $\{C,N\}$ and $n=2$ are $\{CC,CN,NC\}$, so that $\color{blue}{a_1=2}$ and $\color{blue}{a_2=3}$.


We finally get Fibonacci-numbers $a_n$:
\begin{align*}
\begin{array}{r|rrrrrrrr}
n&1&2&3&4&5&6&7&8\\
a_n&2&3&5&8&13&21&34&\color{blue}{55}\\
\end{array}
\end{align*}
and conclude there are $\color{blue}{a_8=55}$ valid words of length $8$.

