Recursively defining sets of strings discrete math

Question

So here are the two problems:

1. Recursively define the set of bit strings K that do not have 00 as its substring.

2. How many bit strings of length 10 are included in the above set K?

Can someone please solve it and explain to me what's going on at each step? Thank you!

Answer 1

Let $1_n$ be the set of such strings of length $n$ ending in $1$. Similarly let $0_n$ be the set of such strings ending in $0$. Then we have $$ \begin{align} 1_{n+1}&=\{x\parallel 1\mid x\in 1_n\cup 0_n\}\\ 0_{n+1}&=\{x\parallel 0\mid x\in 1_n\} \end{align} $$

---

Define $A_n=|1_n|$ and $B_n=|0_n|$. Then we have from above $$ \begin{align} A_{n+1}&=A_n+B_n\\ B_{n+1}&=A_n \end{align} $$ with $A_1=B_1=1$ and thus $A_2=2$. Combining those we get $$ A_{n+1}=A_n+A_{n-1} $$ also known as the Fibonacci recurrence relation. Hence $$ A_n=F_n=\frac{(1+\sqrt 5)^2+(1-\sqrt 5)^n}{2^n\sqrt 5} $$ and the number you seek is $$ A_{10}+B_{10}=F_{10}+F_{9}=89+55=144 $$

Answer 2

Let $S$ be this set, and $\epsilon$ be the empty string.

Define $S_0 ::= 0S_*$ and $S_* ::= \epsilon \mid 1S_0 \mid 1S_*$.

$S ::= S_0 \mid S_*$.

This is BNF notation.

---

Let $u_n$ be the number of strings of length $n$ in $S_0$, and $v_n$ be the number of strings of length $n$ in $S_*$.

We have $u_n = v_{n-1}$ and $v_n = u_{n-1} + v_{n-1}$. $u_0$ = 0 (because $u_0$ counts the number of strings of length 0 that end in a $0$), and $v_0$ = 1.

$$ \left[ \begin{array}\\ u_{n+1} \\ v_{n+1} \end{array} \right] = \left[ \begin{array}\\ 0 & 1 \\ 1 & 1 \end{array} \right] \left[ \begin{array}\\ u_{n} \\ v_{n} \end{array} \right] $$

Call the matrix above $M$. Diagonalise the matrix into the form $D = PMP^{-1}$, and then notice that $M^n = P^{-1}D^nP$.

The answer to your question is then $u_{10} + v_{10}$.