On the other hand, if $b_n=0,$ then by assumption, $b_{n-1}$ must be $1.$

This shows that $S_n=S_{n-1}+S_{n-2},$ which completes the proof.

Therefore the number of $n-$bit strings with last digit $1$ is $S_{n-1}.$

Since $0,1$ are the $1-$bit strings without the pattern $00,$ and $11,01,10$ are the $2-$bit strings without the pattern $00,$ we have $S_1=2=f_3$ and $S_2=3=f_4.$

Let $b_1{b}_{2}dots{b}_n$ be an $n-$bit string without the pattern $00.$

Then $b_{1}dots{b}_{n-2}$ can be any $(n-2)-$bit string without the pattern $00.$

Therefore the number of $n-$bit strings with last digit $0$ is $S_{n-2}.$

It suffices to show that $S_n$ and $f_{n+2}$ have the same initial conditions and the same recurrence relation, i$.$e$.,S_1=f_3$ and $S_2=f_4,$ and $S_n=S_{n-1}+S_{n-2}$ for $n3.$

If $b_n=1,$ then $b_{1}dots{b}_{n-1}$ can be any $(n-1)$ bit string without the pattern $00.$

Now it remains to show that $S_n=S_{n-1}+S_{n-2}$ for $n3.$