Combinatorics on letters How many "words" of length n is it possible to create from {a,b,c,d} such that a and b are never next to each other?
 A: Let the total number of such words on $n$ letters be $s_n$. Let the number of words which end with $a$ be $a_n$ and the number of words which end with $b$ be $b_n$.
Now consider a word on $n-1$ letters. We may add $c$ or $d$ to the end of the word to obtain a new word on $n$ letters. Conversely, all words on $n$ letters which end with $c$ or $d$ can be obtained in this way. Now to any word not ending with $a$ we may add $b$ to the end. To any word not ending in $b$ we may add $a$ to the end. All words ending with $a$ or $b$ are obtained in this fashion. 
Therefore we have the recurrence for $a_n$ and $b_n$ as
$$s_n = 2s_{n-1} + (s_{n-1}-a_{n-1}) + (s_{n-1}-b_{n-1})=4s_{n-1} - a_{n-1} - b_{n-1}$$
Similarly, the number of words which end with $a$ or $b$ are given by
$$a_n = s_{n-1}-b_{n-1}$$
$$b_n = s_{n-1}-a_{n-1}$$
By symmetry, we must have $a_n = b_n$, so we will work solely with $a_n$ from now on. The above gives us two coupled recurrences
$$s_n = 4s_{n-1} - 2a_{n-1}$$
$$a_n = s_{n-1} - a_{n-1}$$
We can combine the two as a single recurrence for $a_n$
$$a_{n} = 3a_{n-1} + 2a_{n-2}$$
which has solution
$$a_n = \frac{(3+\sqrt{17})^n - (3-\sqrt{17})^n}{2^n\sqrt{17}}$$
Then we have
$$\begin{align}s_n &= a_{n+1} + a_n 
\\&= \frac{(3+\sqrt{17})^{n+1} - (3-\sqrt{17})^{n+1}}{2^{n+1}\sqrt{17}} + \frac{(3+\sqrt{17})^n - (3-\sqrt{17})^n}{2^n\sqrt{17}}
\\&=\frac{(5+\sqrt{17})(3+\sqrt{17})^n - (5-\sqrt{17})(3-\sqrt{17})^n}{2^{n+1}\sqrt{17}}\end{align}$$
This sequence begins as
$$s_n = 4,\ 14,\ 50,\ 178,\ 636,\ 2258,\ 8042,\ 28642,\ 102010,\ \cdots$$
and is sequence A055099 in OEIS (with a shifted index).
