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.
Strings of length $n$ formed by $a,b,c$ where $a$ and $b$ are not adjacent
combinatorics
Best Answer
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)\ .$$