Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0 I am preparing for my finals for discrete mathematics and I came across this exercise in textbook.
Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not contain substring $00$, $01$ and the last symbol is not $0$. Find: 


*

*non recurrent sum for $s_{n}$ using combinatorics

*recurrence relation $s_{n}$.
I managed to find recurrence relation ${s}'_{n} = 2s_{n-1} + s_{n-2}$ that satisfies the first two conditions (no $00$'s and $01$'s) but I have no idea how to find RR with all three conditions. My first thought was to make some correction in initial conditions, but after trying it I got even more confused.
As for the sum, I'm lost as well.
Can you point me in the right direction towards solution?
 A: Observe that the conditions you are given are equivalent to the single condition that "every $0$ must be immediately followed by a $2$."  In particular, this means that any such sequence of length $n$ is either (a) such a sequence of length $n-1$ with a $1$ or $2$ appended to the end, of which there are $2s_{n-1}$, or (b) such a sequence of length $n-2$ with a $02$ appended to the end, of which there are $s_{n-2}$.  (Also note that these cases are mutually exclusive since strings from the first case can't have a $0$ as the second-to-last symbol.)  This gives your recurrence $s_n = 2s_{n-1} + s_{n-2}$.  For the initial conditions, you get $s_1 = 2$ and $s_2 = 5$ (just count these by hand).
You can use the same equivalent condition above to write a combinatorial sum.  You can think of this as an unrestricted string with three different symbols: $a=1$, $b=2$, and $c=02$, where the third symbol $c$ takes up two spots.  If there are $k$ copies of the symbol $c$ in a string of length $n$, then there must be a total of $n-k$ symbols $a, b, c$.  Try to write an expression for the number of such strings with $k$ copies of $c$, and then sum over all possible values of $k$ for your answer.   (Since this is homework, I'll let you take it from here.)
A: You simply have that every $0$ must be followed by a $2$, so $s_n$ is the number of arrangements of $a$ blocks of type "$02$", $b$ blocks of type "$1$" and $c$ blocks of type "$2$" such that $2a+b+c=n$. On the other hand, every admissible string starts with a "1", then the tail is counted in $s_{n-1}$, with a $2$, then the tail is counted in $s_{n-1}$, or with a $02$, then the tail is counted in $s_{n-2}$, and recurrence relation is $s_n=2s_{n-1}+s_{n-2}$, with $s_1=2$ and $s_2=5$. The recurrence relation and the initial conditions give:
$$ s_n = c_0(1+\sqrt{2})^n+c_1(1-\sqrt{2})^n, $$
$$c_0(1+\sqrt{2})+c_1(1-\sqrt{2}) = 2,$$
$$c_0(3+2\sqrt{2})+c_1(3-2\sqrt{2})=5,$$
$$ c_0-c_1=\frac{\sqrt{2}}{2},$$
$$ c_0+c_1=1, $$
$$ c_0 = \frac{2+\sqrt{2}}{4},\qquad c_1=\frac{2-\sqrt{2}}{4}$$
$$ s_n = \frac{1}{2}\left(p_{n+1} + p_{n}\right), \qquad p_n = \frac{1}{2}\left((1+\sqrt{2})^n+(1-\sqrt{2})^n\right),$$
where $p_n$ is half the Pell-Lucas number $Q_n$. In a combinatorial flavour, you can count the arrangements of $a$ blocks of type "$02$" (with $a\leq\frac{n}{2}$) in $n$ positions times $2^{n-2a}$ (the number of ways to fill the remaining part of the string with $1$s and $2$s). The number 
of such arrangements is equal to the number of ways to write $n-2a$ as a sum of $a+1$ natural numbers, so the coefficent of the monomial $x^{n-2a}$ in $(1+x+x^2+\ldots)^{a+1}=\frac{1}{(1-x)^{a+1}}$, that is $\binom{n-a}{a}$. 
This gives:
$$ s_n = \sum_{a=0}^{\lfloor n/2\rfloor}\binom{n-a}{a}2^{n-2a}. $$
