(CHECK) $n$-bit Strings Containing a Pattern

Question

---

$$\text{$\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}$}$$

---

If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and initial conditions for the sequence $\{S_n\}$?

What I'm writing down now:

---

Is this $f_{n+2}$? Here $f_n$ denotes the $n^{\text{th}}$ Fibonacci number.

Answer 1

HINT: Suppose that $\sigma$ is an $n$-bit string that does not contain $00$. To get an $(n+1)$-bit string not containing $00$ you can certainly append a $1$, so there are $S_n$ acceptable $(n+1)$-bit strings that end in $1$. You can append a $0$ if and only if $\sigma$ ends in $1$. Use the previous sentence to determine how many acceptable $n$-bit strings end in $1$, and add that to $S_n$ to get your recurrence for $S_{n+1}$. I’ll leave the initial conditions for you: once you have the recurrence, you’ll know how many you need, and it’s completely straightforward to count short bit strings not containing $00$. (You do need to remember that the empty bit string does not contain $00$!)

Answer 2

---

Answer:

$2S_{n-2}+S_{n-3}$

---

Reason:

There are three cases:

$(a)\hspace{1cm}\text{The string starts with 0}$

$(b)\hspace{1cm}\text{The string starts with 10}$

$(c)\hspace{1cm}\text{The string starts with 11}$

For $(a)$ the next bit is necessarily $1$ by the conditions of the problem, so since the next $n-2$ bits are strings without $00$, then there are $S_{n-2}$ such strings. Similarly, for $(b)$ the next bit is a $1$ by the conditions of the problem, so since the next $n-3$ bits are strings without $00$, then there are $S_{n-3}$ such strings. Lastly, for $(c)$ there are $n-2$ such strings as the third bit can be either $1$ or $0$. Hence, by the principle of addition, the total is the sum of cases $(a), (b),$ and $(c)$, namely $S_n=2S_{n-2}+S_{n-3}$ with $S_0=1$, $S_1=2$, and $S_2=3$.

---

int S( int n ){

if( n == 0 )
    return 1;
if( n == 1 )
    return 2;
if( n == 2 )
    return 4;
if( n == 3 );
    return 7;
return 2*S( n - 2 ) + S( n - 1 );

}

Answer 3

A number written in the series of $1$ and $0$, where $00$ does not appear, is the ones-complement of the fibonacci count (where $11$ is not permitted). One can then write the number out in this style

       144  89  55  34  21  13  8  5  3  2  1
         0   1   0   0   1   0  1  0  0  1  0   =  120

When two '1's are adjacent, then one can 'jump' by the series that $11=100$. One can show that by feeding numbers at the bottom, that all possible allowed patterns occur, and that one gets whatever $100000000$ might represent. So a string of 11 digits above, we would find the maximum is the the first unwritten number or $F_{13}$.