Strings of length $n$ formed by $a,b,c$ where $a$ and $b$ are not adjacent Consider the strings of length $n$ formed by the letters $a,b,c$, and also requiring the letters $a,~b$ are not adjacent. How many such string? My first attempt was inclusive-exclusive formula or simple counting technique, but I think it wouldn't work. And also the numbers of $a$ and $b$ is uncertain, so it brings the problem to a more difficult circumstance.
 A: Let $A(n)$ be the number of strings of length $n$ ending in $a$ and $B(n), C(n)$ similar.  Now define coupled recurrences between the three.  You can just enter it in a spreadsheet and copy down.  By symmetry $A(n)=B(n)$ and $C(n+1)$ is the number of strings of length $n$ because you can add a $c$ to any string.  I get a total of $19601$ strings of length $11$
To get an analytic solution you can then make a $3 \times 3$ matrix that updates $\begin {pmatrix} A(n)\\B(n)\\C(n) \end {pmatrix}$ to length $n+1$.  Now find the eigenvalues and eignevectors and express your starting condition $A(1)=B(1)=C(1)=1$ in terms of them.  The leading eigenvalue is $1+\sqrt 2$
A: Let $s_n$ count the admissible strings of lenth $n\geq0$, and $c_n$ the admissible strings of length $n$ not ending in $a$ or $b$. Then
$$s_0=c_0=1,\quad s_1=3\ .\tag{1}$$
If an admissible word  ends in $a$ or $b$ there are two options for the next letter, otherwise three. Furthermore we can always append a $c$. It follows that we have
$$s_{n+1}=2s_n+c_n,\qquad c_{n+1}=s_n\ .$$
Eliminating $c_n$ we obtain the recursion
$$s_{n+1}=2s_n+s_{n-1}\qquad(n\geq1)\tag{2}$$
with characteristic polynomial $\lambda^2-2\lambda-1$. The roots are $1\pm\sqrt{2}$, so that the general solution of $(2)$ is
$$x_n=A\bigl(1+\sqrt{2}\bigr)^n + B\bigl(1-\sqrt{2}\bigr)^n\qquad(n\geq0)\ .$$
Using $(1)$ we then obtain 
$$s_n={\bigl(1+\sqrt{2}\bigr)^{n+1} +\bigl(1-\sqrt{2}\bigr)^{n+1}\over2}\qquad(n\geq0)\ .\tag{3}$$
As the second term in $(3)$ is rapidly decreasing we may write
$$s_n={\rm round}\left({1\over2}\bigl(1+\sqrt{2}\bigr)^{n+1} \right)\qquad(n\geq0)\ .$$
