Solution: 2019 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 = 2 \cdot S_{n - 1}$

(b)

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

(c)

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

(d)

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

Solution

Um, let’s just sum all possible recursive functions:

$+3,S_{n-3}$
$+4,S_{n-4}$

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