Solution: 2022 Winter Final - 8

Author: Michiel Smid

Question

Let $n\ge 1$ be an integer and let $S_n$ be the number of ways in which $n$ can be written as a sum of $1$'s and $3$'s, in which the order of the terms matters. For example, $S_4=3$ because \[ 4 = 1+1+1+1 = 1+3 = 3+1 \enspace . \] Which of the following is true, for any integer $n\ge 4$:

(a)

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

(b)

$S_n=3S_{n-1}$

(c)

$S_n=3S_{n-3}$

(d)

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

(e)

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

Solution

Recursive Formula Explanation

Case 1: If the first term is 1

If the first term is 1, the remaining sum is $n - 1$.
The number of ways to write $n - 1$ as a sum of 1’s and 3’s is $S_{n-1}$.

Case 2: If the first term is 3

If the first term is 3, the remaining sum is $n - 3$.
The number of ways to write $n - 3$ as a sum of 1’s and 3’s is $S_{n-3}$.

Since these two cases cover all possible scenarios of writing any sum given the constraints in the question above (the first number must either be 1 or 3), the total number of ways is: $S_n = S_{n-1} + S_{n-3}$