Question: 2015 Winter 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 1s.

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