Auto Generated Question

Back

1 . For each integer

n \geq 0

, let

S_{n}

denote the number of length-

n

strings over the alphabet

{a, b, c}

that do not contain

a a

b b

. Which of the following is true, for any integer

n \geq 1

(a)

S_{n} = S_{n - 1} + \sum_{i = 1}^{n} 2 S_{n - i}

(b)

S_{n} = S_{n - 1} + 2 S_{n - 2}

(c)

S_{n} = S_{n - 1} + \sum_{i = 0}^{n - 2} S_{i}

(d)

S_{n} = S_{n - 1} + \sum_{i = 0}^{n - 2} 2 S_{i}

(e)

S_{n} = S_{n - 1} + 4 S_{n - 2}