Question: 2017 Winter Final - 7
In this question, we consider bitstrings of length $n$, where $n$ is an even integer, and in which
the positions are numbered $1,2,\dots,n$.
For any even integer $n$, let $S_n$ be the number of bitstrings of length $n$ that have both of the following two properties:
For any even integer $n$, let $S_n$ be the number of bitstrings of length $n$ that have both of the following two properties:
- There is a 0 at every even position.
- The entire bitstring does not contain the substring 101.
(a)
$S_n = S_{n-2} + S_{n-4}$
(b)
$S_n = S_{n-2} + S_{n-3}$
(c)
$S_n = S_{n/2} + S_{(n/2)-3}$
(d)
$S_n = S_{n-1} + S_{n-3}$