Solution: 2018 Fall Final - 8

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 2's and 4's; the order in which the 2's and 4's occur in the sum matters. For example, $S_6 = 3$, because $$ 6 = 2 + 2 + 2 = 2 + 4 = 4 + 2. $$ Which of the following is true for any integer $n \geq 6$?

(a)

$S_n = S_{n-2} + 4 \cdot S_{n-4}$

(b)

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

(c)

$S_n = 2 \cdot S_{n-2} + S_{n-4}$

(d)

$S_n = 2 \cdot S_{n-2} + 4 \cdot S_{n-4}$

Solution

Let’s write out the possibilities and sum them

$2, S_{n-2} $

$4, S_{n-4} $

The reason this works is because it’s as if we have n balls. We have baskets that can store 2 balls and baskets that can store 4 balls.

We can choose to put 2 balls in the 2-ball basket or in the 4-ball basket

Every time we use one of the baskets, we subtract by that number of balls

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