Question 182
Given $k \in \{0, 1, 2, 3\}$ and a positive integer $n$, let $f_k(n)$ be the number of sequences $x_1, \dots, x_n$, where $x_i \in \{-1, 0, 1\}$ for $i = 1, \dots, n$, and
$$
x_1 + \cdots + x_n \equiv k \mod 4.
$$
a. Prove that $f_1(n) = f_3(n)$ for all positive integers $n$.
b. Prove that
$$
f_0(n) = \frac{3^n + 2 + (-1)^n}{4}
$$
for all positive integers $n$.
$$
x_1 + \cdots + x_n \equiv k \mod 4.
$$
a. Prove that $f_1(n) = f_3(n)$ for all positive integers $n$.
b. Prove that
$$
f_0(n) = \frac{3^n + 2 + (-1)^n}{4}
$$
for all positive integers $n$.