1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I see, so the other way must be considered. $\endgroup$ – Trancot Jul 29 '13 at 3:06
  • $\begingroup$ What explains the $S_1$? $\endgroup$ – Trancot Jul 29 '13 at 4:35
  • $\begingroup$ What is $S_0$? Do we have to consider that? $\endgroup$ – Trancot Jul 29 '13 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.