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=S_{n-1}+S_{n-2}$

(c)

$S_n=3S_{n-3}$

(d)

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

(e)

$S_n=3S_{n-1}$

Solution

Let’s just sum up all possibilities as a recursion thing

$1, S_{n-1} $

$3, S_{n-3} $

$ Sn = S{n-1} + S_{n-3} $