Strings of length $n$ formed by $a,b,c$ where $a$ and $b$ are not adjacent

Question

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.

Answer 1

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

Answer 2

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$