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?
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.