Combinatorics on letters

Question

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?

Answer 1

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).