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 ?
 A: For problems like this the Goulden-Jackson Cluster Method is a convenient method to derive a generating function. The coefficients of this function are the wanted numbers.

We consider the set of words in $ \mathcal{V}^{\star}$ of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{a,b,c,d\}$$ and the set $B=\{ab,ba\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a function $f(s)$ with the coefficient of $s^n$ being  the number of wanted words of length $n$.
According to the paper (p.7) the generating function $f(s)$  is
  \begin{align*}
f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
  with $d=|\mathcal{V}|=4$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with
  \begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[ab])+\text{weight}(\mathcal{C}[ba])
\end{align*}
  We calculate according to the paper
  \begin{align*}
\text{weight}(\mathcal{C}[ab])&=-s^2-\text{weight}(\mathcal{C}[ba])s\\
\text{weight}(\mathcal{C}[ba])&=-s^2-\text{weight}(\mathcal{C}[ab])s\\
\end{align*}
  and get
  \begin{align*}
\text{weight}(\mathcal{C}[ab])=\text{weight}(\mathcal{C}[ba])=-\frac{s^2}{1+s}
\end{align*}
It follows
  \begin{align*}
f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-4s+\frac{2s^2}{1+s}}\\
&=\frac{1+s}{1-2s-3s^2}
\end{align*}

Partial fraction decomposition and expansion of $f(s)$ results in

\begin{align*}
f(s)&=
\frac{1}{2}\left(1+\frac{5}{\sqrt{17}}\right)\cdot\frac{1}{1-\frac{3+\sqrt{17}}{2}s}+\frac{1}{2}\left(1-\frac{5}{\sqrt{17}}\right)\cdot\frac{1}{1-\frac{3-\sqrt{17}}{2}s}\\
&=\frac{1}{2}\left(1+\frac{5}{\sqrt{17}}\right)\sum_{n=0}^\infty\left(\frac{3+\sqrt{17}}{2}\right)^ns^n
+\frac{1}{2}\left(1-\frac{5}{\sqrt{17}}\right)\sum_{n=0}^\infty\left(\frac{3-\sqrt{17}}{2}\right)^ns^n\\
&=1+4s+14s^2+50s^3+178s^4+634s^5+\mathcal{O}(s^6)
\end{align*}

A: 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.
A: From @shardulc 's analysis it follows that
$$k_n=p_n+q_n=(p_{n-1}+q_{n-1}+q_{n-1})+2k_{n-1}=3 k_{n-1}+2k_{n-2}\ ,$$
or
$$k_n-3k_{n-1}-2k_{n-2}=0\qquad(n\geq2)\ ,\tag{1}$$
with the initial conditions $k_0={1\over2}q_1=1$, $k_1=4$. We now proceed according to the rules of the Master Theorem. The characteristic equation $\lambda^2-3\lambda-2=0$ of $(1)$ has the roots $\lambda_\pm={1\over2}(3\pm\sqrt{17})$. It follows that there are constants $c_+$ and $c_-$ with
$$k_n=c_+{\lambda_+}^n +c_-{\lambda_-}^n\qquad(n\geq0)\ .$$
The initial conditions then determine the two constants, and one obtains definitively
$$k_n={1+5/\sqrt{17}\over2}\left({3+\sqrt{17}\over2}\right)^n +{1-5/\sqrt{17}\over2}\left({3-\sqrt{17}\over2}\right)^n\qquad(n\geq0)\ .\tag{2}$$
Here the second term is already for $n=0$ negligible, so that we can replace $(2)$ by
$$k_n={\rm round}\left({1+5/\sqrt{17}\over2}\left({3+\sqrt{17}\over2}\right)^n \right)\ .$$
The numbers produced in this way are
$$1,\quad4,\quad 14,\quad 50,\quad 178,\quad 634,\quad 2258,\quad 8042,\quad 28642, \quad102010,\quad 363314,\ \ldots\ .$$
