Solution: 2015 Winter 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 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?

(a)

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

(b)

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

(c)

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

(d)

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

Solution

Let’s suppose we have a string of 1s and 2s.

We can write down some possibilities.

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

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

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