A $110-$free bitstrings is a bitstring in which the substring $110$ does not occur. Thus

$101000101111$ is $110-$free, and

$101000101110$ is NOT $110-$free.

Let $S_n$ be the number of $110-$free bitstrings of length $n.$

$($a$)$ Find $S_1,S_2,$ and $S_3.$

$($b$)$ For $n4,$ find a recursive expression for $S_n.$

$($c$)$ Bonus: Find a closed form for $S_n,$ either directly, or by relating it to a number that we

have seen on this assignment $($perhaps in a question after this one$)$ or in class. Hint: it

might not exactly match something you have seen, but you will get something similar.