# number of ternary strings with restrictions

How many ternary strings over alphabet {0,1,2} are there which do not contain 2 or more consecutive non-zero characters?

I have figured out recursive relation which is $f_n=f_{n-1}+2\cdot f_{n-2}$ where $f_1=3$ and $f_2=5$

I am looking for combinatorial solution (using sums and combination numbers).

what I tried so far was $\sum_{k=\lfloor n/2\rfloor}^n \binom{n}{k}2^{n-k}$, i choose k zeros and for the remaining $n-k$ spaces I choose either $1$ or $2$, k must be $\lfloor n/2\rfloor$ because if there are less then there exist no such string, but this fails for $n=3$ since it counts string $0xx$ and and $xx0$ as valid where $x$ can be $1$ or $2$

examples: 12000102 is not valid string because it contains 12, 00102000202 is valid

Any ideas?

Edit: another idea is to view all consecutive zeros as a separators, where i can shrink them into one and then fill remaining free slots with 1s and 2s

• In this case there is a straightforward closed form solution of the shape $a2^n +b(-1)^n$. No combinatorial expression can match this in simplicity. – André Nicolas Dec 20 '15 at 17:48
• While this is not as simple as the solution to the recursive relation, you can write the answer as $\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n+1-k}{k}\cdot 2^k$ – user84413 Dec 20 '15 at 17:51
• how did you get this sum – lllook Dec 20 '15 at 17:56
• I explained this in an answer below. – user84413 Dec 20 '15 at 18:03

Let $k$ be the number of nonzero digits, so there are $2^k$ choices for these digits.
which leaves $n-k-(k-1)=n-2k+1$ zeros left to distribute, with the $k$ nonzero digits as dividers.
Since there are $\dbinom{n-k+1}{k}$ ways to distribute these zeros,
there are a total of $\displaystyle\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-k+1}{k}\cdot 2^k$ such words.