Question

a)Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s. b) What are the initial conditions? c) How many ternary strings of length six do not contain two consecutive 0s?

Answer 1

Answer: Denote by $a_n$ the number of ternary strings of length n

• a) $a_n=2(a_{n-1}+a_{n-2})$ for all  $n\geq 3$.

• b) $a_1=3, a_2=8$

• c) 284

Step-by-step explanation:

a) Let $S=x_1 x_2\cdots x_{n-2} x_{n-1} x_{n}$ be a ternary string of length n. If $x_{n}=1$, then S can be decomposed as $S=L1$ where $L$ is a ternary string of length n-1 with no consecutive zeros. In this case, there are $a_{n-1}$ choices for $L$ therefore the number of strings S which last is digit 1 is $a_{n-1}$. Similarly, the number of ternary strings S with $x_{n}=2$ is $a_{n-1}$. We conclude that the number of strings S whose last digit is 1 or 2 is $2a_{n-1}$

Now, if $x_{n}=0$, then $x_{n-1}=1$ or $x_{n-1}=2$ because S does not have consecutive zeroes. Then $S=P10$ or $S=P20$ where $P$ is a ternary string of length n-2 with no consecutive zeros. Thus, the number of such strings S is equal to the number of strings P whose last digit is 1 or 2 is $2a_{n-1}$. Applying the same reasoning from before, this number is equal to  $2a_{n-2}$.

Any string S has its last digit equal to 0,1 or 2 then by the sum rule, $a_n=2a_{n-1}+2a_{n-2}=2(a_{n-1}+a_{n-2})$.

b) 0,1,2 are the strings of length 1 with no consecutive zeroes. Then $a_1=3$. The corresponding strings of length 2 are 01,02,10,11,12,20,21,22, thus $a_2=8$.

c) This follows froma applying the recurrence relation repeatdly. $a_6=2a_{5}+2a_{4}=2(a_4+a_3)+2a_4=4a_4+2a_3=8(a_3+a_2)+2a_3=10a_3+8a_2=20(a_2+a_1)+8(a_2)=20(11)+8(8)=284$.