Solution: 2015 Fall Midterm - 12

Author: Michiel Smid

Question

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?

(a)

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

(b)

$S_n = S_{n-2} + S_{n-3}$

(c)

$S_n = S_{n-1} + S_{n-2} + S_{n-3}$

(d)

$S_n = S_{n-1} + S_{n-3}$

Solution

We can write down some valid possibilities first.

$1, S_{n-1}$ possibilities left

$2, 1, S_{n-3}$ possibilities left

$S_n = S_{n-1} + S_{n-3}$