# 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?

• So sorry, I had a bug in my program and I don't have the source code with me. Of course, $s_{1} = 2$, due to the fact that only strings satisfying those conditions are $1$ and $2$. I removed the table to avoid any further confusion. – user110409 Dec 11 '13 at 10:18
• I seem to be getting $s_n=2s_{n-1}+s_{n-2}$. Are you sure that's wrong? – bof Dec 11 '13 at 11:02

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.)
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}.$$