Question: 2015 Fall Midterm - 12

Let $n \geq 1$ be an integer and let $S_n$ be the number of ways in which $n$ can be written as a sum of 1s and 2s, such that

• the order in which the 1s and 2s occur in the sum matters, and
• it is not allowed to have two consecutive 2s.

For example, if $n = 7$, then both $$ 7 = 1 + 2 + 1 + 2 + 1 $$ and $$ 7 = 2 + 1 + 1 + 2 + 1 $$ are allowed, whereas $$ 7 = 1 + 2 + 2 + 1 + 1 $$ is not allowed.
Which of the following is true?