Ternary strings (combinatorics, recurrence) The questions is: for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$. Provide answer in form of:
a) recurrence relation
b) combinatorial expression 
After that, for $B_n$ take $A_n$ and exclude strings that also have substring $”12”$ and end with $”1”$ (at the same time).
The biggest issue for me comes with combinatorial expression, whatever I try I cannot include all variations and get kind of lost. Might appreciate a bit of help on recurrence relation as well. 
 A: Know this is old, but this is an interesting problem! Let A be a ternary string of length $n$ which does not include the substring $11$. If A does not end in a $1$, then A can be broken up into a unique sequence of the atomic strings $0$, $2$, $10$ and $12$; each $1$ must be followed by a $0$ or $2$, and any remaining characters are either $0$ or $2$. Conversely any string of length $n$ comprised of these atomic strings meets our conditions.
To count the number of such strings of length $n$, let $i$ be the number of length 2 atoms ($10$ and $12$) in the string. The total number of strings of length $n$ using $i$ length 2 atoms from our set is ${{n-i}\choose{i}}2^{n-i}$. To see this, note that we need $i$ length 2 atoms and $n-2i$ length 1 atoms to create a string of length $n$, so a total of $n-i$ atoms. From the $n-i$ available positions in the string, we pick $i$ positions to get length 2 atoms, and once they are picked, there are $2^i$ ways to fill in length 2 atoms. The remaining $n-2i$ positions are filled with length 1 atoms, which can be done in $2^{n-2i}$ ways.
So the total number of length $n$ strings not ending in a $1$ with no $11$ substring is $\sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor}{{n-i}\choose{i}}2^{n-i}$.
The number of such strings that do end in a $1$ is calculated similarly, noting that such a string is comprised of a string of length $n-1$ with no $11$ substring that does not end in a $1$, followed by a $1$. Hence there are $\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{{n-1-i}\choose{i}}2^{n-1-i}$ such strings.
Thus $A_n = \sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor}{{n-i}\choose{i}}2^{n-i} + \sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{{n-1-i}\choose{i}}2^{n-1-i}$.
A: I happened to chance on this, so here is the combinatorial approach that you wanted, which is incidentally much simpler !
Hope you like it !
Combinatorial approach
Any string of $i$ non-$1's$ create $(i+1)$ gaps (including ends) where non-adjacent $1's$ can be put,
thus if string length is $n$, the minimum number of non $1's$ needed is $\lfloor\frac{n}2\rfloor$ to ensure that no $1's$ are adjacent.
and in the $(i+1)$ gaps, we just need to fit in the $(n-i)\;\;1's$
$$f(n) = \sum_{i={\lfloor\frac{n}2\rfloor}}^n\binom{i+1}{n-i}$$
