Question: 2022 Winter Final - 9
For each integer $n\ge 0$, let $S_n$ denote the number of length-$n$ strings over the alphabet $ \{a,b,c\} $ that do not contain $aa$ or $bb$.
Which of the following is true, for any integer $n\ge 1$?
(a)
$S_n=S_{n-1} + 2S_{n-2}$
(b)
$S_n=S_{n-1} + \sum_{i=0}^{n-2} 2S_{i}$
(c)
$S_n=S_{n-1} + \sum_{i=0}^{n-2} S_{i}$
(d)
$S_n=S_{n-1} + \sum_{i=1}^{n} 2S_{n-i}$
(e)
$S_n=S_{n-1} + 4S_{n-2}$