The numbers of strings with rules I have 
$x \in \{ 0, 1 ,2 \}$
and I have to find out how many strings of length $n$, satisfying certain rules, I can assemble.
The rules:


*

*The string cannot contain the substring $00$.

*The string cannot contain the substring $01$ and cannot end with $0$.


I have created this formula:
$$\sum_{i=0}^{n} \binom{n-i}{i} 2^{n-2i}$$
$00$ cannot be in the string, and the string cannot end with $0$, so we have
$\binom{n-i}{i}$ combinations. The string cannot contain the substring $00$ nor $01$ so this binomial number tells us also where to put $2$. We have $n^{n-2i}$ places left to put $1$.
Is this correct? Or did I make a mistake somewhere?
Thanks for your help.
 A: Every time there's a $0$, it must be followed by a $2$. There is no requirement that a $1$ be followed by a $2$ though except if it is the last character. Thus we can pick the number of $02$'s, and the rest are free. We can reduce this to counting unrestricted strings by cases of the number of $0$'s. If there are $i$ $0$'s, then there are $\binom{n-i}{i}$ places to put them, and $2^{n-2i}$ ways to select the remaining characters. So the answer is
$$\sum_{i=0}^{\lfloor n/2\rfloor}{\binom{n-i}i2^{n-2i}}$$
Thus I agree with your answer. Your range of summation, $0$ to $n$, is fine if we define $\binom ab=0$ if $a<b$.
A: Let $a_n$ be the number of such strings. Then $a_1=2$ and $a_2=5$, and $a_n= 2a_{n-1}+a_{n-2}$ for all $n \geq 3$, because an acceptable  $n$-string that starts with 1 or 2 may be followed by any acceptable $(n-1)$-string, while a string starting with 0 must be followed by 2 and then any acceptable $(n-2)$-string. This a second order linear recurrence and 
$$a_n = \frac{1}{2\sqrt{2}} \left((1+\sqrt{2})^{n+1} - (1-\sqrt{2})^{n+1} \right)$$
The values match the ones in the answer given by the OP.
