Number of n-words such that a and b are not neighbors. 
Question:How many n-words from the alphabet {a,b,c,d} are such that a and b are never neighbors?

1.There are $4^n$ ways to arrange the four letters.
2.There are $(n-1)$$2^{n-1}$ ways of arranging a and b together.(is it so?)
3.Hence,the required number is $4^n$-$(n-1)$$2^{n-1}$.
Have I counted the right number of things?
I am looking for a very beautiful Combinatoric proof.

Edit:I realized I had incorrectly assumed that a and b occurred only once in the sequence.

 A: I found something with recursion, I don't know if it helps.
Let $s_n$ be the number of $n$-words ending in $a$ (equal to the number of $n$-words ending in $b$) and let $t_n$ be the number of $n$-words ending in $c$ (equal to the number of $n$-words ending in $d$).
Then we have:
$s_{n+1}=s_n+2t_n$ since an $n+1$ word ending in $a$ is obtained by taking a $n$ word ending in $a,c$ or $d$ and adding an $a$ at the end.
$t_{n+1}=2s_n+2t_{n}$ since an $n+1$ $n$-word ending in $c$ is obtained by taking any $n$-word (ending in any of $a,b,c,d$ and adding a $c$ at the end.
Let $f_n$ be then number of $n$-words. Then $f_n=t_{n+1}$ since an $n+1$-word ending in $c$ can be obtained by taking an $n$ word and just attaching a $c$ at the end.
We have the recursion $f_{n+1}=3s_n+3s_n+4t_n+4t_n$ since a $n$-word ending in $a$ can be extended in three ways to an $n+1$-word (likewise for wn $n$-word ending in $b$. On the other hand words ending in $b$ can ended in $4$ ways.
So $f_{n+1}=6s_n+8t_n$, using $s_n+s_n+t_n+t_n=f_n$ we get $f_{n+1}=3f_n+2t_n=3f_n+2f_{n-1}$
So $f_{n+1}=3f_n+2f_{n-1}$.
We could obtain an exponential formula similar to that of the fibonaccis, but I have a gut feeling it will have an irrational coefficient just like the formula for the fibonaccis.
Lets use the recursion to compute some values.
By inspection we have:
$f_1=4,f_2=16-2=14$.
From here:
$f_3=50,f_4=178,f_5=634,f_6=2258,f_7=8042,f_8=28642,f_9=102010,f_{10}=363314$
A: Your formula in step 2 is wrong.
For a counterexample, let's begin to count the number of $3$-words that have $a$ and $b$ as neighbors. Your formula says there should be $(3-1)2^{3-1}=8$ of them. But look at these:
aba
abb
abc
abd

baa
bab
bac
bad

aab
cab
dab

bba
cba
dba

These are more than $8$! (The two groups have the first occurrence of $ab$ or $ba$ as the first two letters, and the next two groups have the first occurrence as the last two letters.)
A: If an $n-1$ word ends in $c$ or $d$, you can extend it to an $n$ word in $4$ ways.  If it ends in $a$ or $b$, you can extend it in three ways, presuming that $aa$ and $bb$ are allowed.  Define $A(n)$ as the number of acceptable $n$ words that end in $a$ or $b$ and $B(n)$ as the number of  acceptable $n$ words that end in $c$ or $d$.  We have
$A(1)=B(1)=2, A(n)=A(n-1)+2B(n-1), B(n)=2A(n-1)+2B(n-1)$
and your answer is $A(n)+B(n)$    
I made an Excel sheet, found $4, 14, 50, 178, 634, 2258, 8042, 28642, 102010, 363314, 1293962, 4608514, 16413466, 58457426$, looked it up in OEIS, and found the generating function $\frac {1+x}{1-3x-2x^2}$
A: By establishing a system of recurrence relations one quickly finds a recurrence relation that can solve this. I will generalise the problem by assuming that the alphabet has $k$ letters without restriction and $l$ letters that cannot be adjacent among each other, except when the letters are identical; the problem in the question is a special case for $k=l=2$.
Let $t_n$ be the number of such words not ending with a restricted letter, and $s_n$ the number of such words ending with a letter among the $l$ restricted ones (I follow the nomenclature used in another answer); we shall ultimately be interested in $t_n+s_n$. The initial values are $t_0=1$, $s_0=0$ (the negative formulation for $t_n$ was to get these cases right). We have for $n>0$ that $t_n=(t_{n-1}+s_{n-1})k$ (one can place an unrestricted letter after and valid word of length $n-1$) and $s_n=t_{n-1}l+s_{n-1}$ (one can either extend a word not ending with a restricted letter by any restricted letter, or extend a word ending with a restricted letter by repeating the final letter). In matrix form one has
$$
  v_n = A\, v_{n-1}\qquad\hbox{where }v_n=\pmatrix{t_n\\s_n}\hbox{ and }A=\pmatrix{k&k\\l&1}
$$
Since the matrix $A$ satisfies $A^2-(k-1)A-k(l-1)I=0$ (since $X^2-(k-1)X+k(1-l)$ is its characteristic polynomial) the vector sequence satisfies the recurrence $v_{n+2}-(k+1)v_{n+1}-k(l-1)v_n=0$ for all $n\in\Bbb N$. The same linear recurrence holds for the numeric sequence $(t_n+s_n)_{n\in\Bbb N}$ that interests us.
We can find a formula for the generating series $S=\sum_{i\in\Bbb N}(t_n+s_n)X^n\in \Bbb Z[[X]]$. The recurrence relation ensures that the product series $S\bigl(1-(k+1)X-k(l-1)X^2\bigr)$ has no nonzero terms of degree${}\geq2$, and from the initial values $t_0+s_0=1$ and $t_1+s_1=k+l$ one concludes that this product equals $1+(l-1)X$. In conclusion
$$
  \sum_{i\in\Bbb N}(t_n+s_n)X^n = \frac{1+(l-1)X}{1-(k+1)X-k(l-1)X^2}
$$
is the generating series for the number of solutions. In particular for $k=l=2$ one finds (without computer aid) the generating series $\frac{1+X}{1-3X-2X^2}$ that Ross Millikan also found.
