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 - 1} + S_{n - 2}$
(b)
$S_n = S_{n - 3} + S_{n - 4}$
(c)
$S_n = S_{n - 2} + S_{n - 3}$
(d)
$S_n = 2 \cdot S_{n - 1}$
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.