$n$-Bit Strings Not Containing $010$

Question

So, I am asked to consider the number of $n$-bit strings that don't contain $010$ by considering the following $m$-leading-zero cases for $m\geq 0$, where $m\in \mathbb{N}$:

$1\cdots$

$01\cdots$

$001\cdots$

$\hspace{.15cm}\vdots$

I'm required to show that these cases will produce the recurrence relation below: $$S_n=S_{n-1}+S_{n-3}+S_{n-4}+\cdots+S_1+3$$ So, I get that the correspondence goes $1\rightarrow S_{n-1}$, $01\rightarrow S_{n-3}$, $001\rightarrow S_{n-4}$, and so on, but where does the "$S_1+3$" expression come from?

vadim123 · Accepted Answer · 2013-07-29T05:46:01.730

1

The reason for the 3 is because the expression doesn't account for $0\ldots 011$, $0\ldots 001$, or $0\ldots 000$. Also note that the relation holds only for $n\ge 3$.

$S_1=2, S_2=4, S_3=7$. The recurrence counts $100, 101, 110, 111$ for $S_3$, but none of the others.

More details:

$S_3=S_2+3$
$S_4=S_3+S_1+3$
$S_5=S_4+S_2+S_1+3$

This comes because we may begin with 1 (followed by any of $S_{n-1}$), or we may begin with $011$ (followed by any of $S_{n-3}$), or we may begin with $0011$ (followed by any of $S_{n-4}$), $\ldots$, or we may begin with $0\ldots 011$ (followed by any of $S_1$), or we may have any of the three extra strings I listed at the top.

edited Jul 29 '13 at 05:46

answered Jul 29 '13 at 02:31

vadim123

82,796

I see, so the other way must be considered. – Trancot Jul 29 '13 at 03:06
What explains the $S_1$? – Trancot Jul 29 '13 at 04:35
What is $S_0$? Do we have to consider that? – Trancot Jul 29 '13 at 04:55

$n$-Bit Strings Not Containing $010$

1 Answers1

Linked