<s>[INST] The number of words of length $n$ from specific alphabet with rule of creating. Determination of the number of words of length n formed from the alphabet $\{ a, b , c, d \} $, where the letters $a , b $ are not adjacent.
How to find out a recurrence and explicit formula for it ?
 [/INST] If $a$ and $b$ are not adjacent in a sequence, we call it a valid sequence. Let the number of valid sequences of length $n$ ending with $a$ or $b$ be $p_n$, and let the number of valid sequences of length $n$ ending with $c$ or $d$ be $q_n$. Let the total number of valid sequences of length $n$ be $k_n$.
The first equation is
$$k_n = p_n + q_n$$
We also know
$$p_n = p_{n-1} + 2q_{n-1}$$
because a sequence ending with $a$ or $b$ can be formed by appending a $b$ or a $a$ to a sequence in $p_{n-1}$ ending with $a$ or $b$ (respectively), or by appending $a$ or $b$ to any sequence in $q_{n-1}$. Also,
$$q_n = 2k_{n-1}$$
as we can append $c$ or $d$ to any valid sequence of length $n-1$.
Using these three, we can write
$$
\begin{align}
k_n &= p_n + q_n \\
&= p_{n-1} + 2q_{n-1} + 2k_{n-1} \\
&= p_{n-2} + 2q_{n-2} + 4k_{n-2} + 2k_{n-1} \\
&= \ldots \\
&= p_1 + 2q_1 + 4k_1 + 4k_2 + \dotsb + 4k_{n-2} + 2k_{n-1} \\
&= p_1 + 2q_1 + 4(k_1 + k_2 + \dotsb + k_{n-2}) + 2k_{n-1}
\end{align}
$$
We see that $p_1 = 2$ and $q_1 = 2$, and $k_1 = 4$. Thus
$$k_n = 4(k_1 + k_2 + \dotsb + k_{n-2}) + 2k_{n-1} + 6$$
Though we cannot solve this recurrence directly, the first few values of $k_n$ are $4, 14, 50, 178, 634$ for $n = 1, 2, 3, 4, 5$. According to OEIS, there is only the closed-form
$$k_n = \frac{5+\sqrt{17}}{2\sqrt{17}} \cdot \bigg(\frac{3+\sqrt{17}}{2}\bigg)^n - \frac{5-\sqrt{17}}{2\sqrt{17}} \cdot \bigg(\frac{3-\sqrt{17}}{2}\bigg)^n$$
as obtained by @ChistianBlatter.
</s>