Solution: 2016 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 3s and 4s, such that the order in which the 3s and 4s occur in the sum matters. For example, $S_5 = 0$, because 5 cannot be written as a sum of 3s and 4s. We have $S_{11} = 3$, because

$11$	$= 3 + 4 + 4 = 4 + 3 + 4$ $= 4 + 4 + 3.$

Which of the following is true for any $n \geq 5$?

(a)

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

(b)

$S_n = 2 \cdot S_{n - 1}$

(c)

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

(d)

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

Solution

We can write down some possibilities first.

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

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

Thus, there are $ S_n = S_{n-3} + S_{n-4} $ possibilities.