By direct calculation, one can obtain
$$f_n(x) = (2x-1)^n + (x+1)^n$$
for all positive integers $n$. Let $Q(x) = x^3 - x^2 + x = x(x^2 - x + 1)$ and $n$ be the natural number such that $Q(x)$ is a divisor of $f_n(x)$. It is easy to see that
$$(-1)^n + 1^n = f_n(0) = 0,$$
then $n$ is odd.

Let $R(x) = \frac{f_n(x)}{Q(x)}$, we will show that $R(x)$ is an integer coefficient polynomial. In this step, we assume that
$$R(x) = \frac{aR_1(x)}{b},$$
where $a, b \in \mathbb{Z}^+$ and $R_1(x)$ is a primitive polynomial. Hence,
$$b f_n(x) = a R_1(x) Q(x).$$
By Gauss lemma, $R_1(x)Q(x)$ is primitive then the greatest common divisor of all the coefficients of $aR_1(x)Q(x)$ is $a$ hence $a$ is divisible by $b$. Denoted $a = b \cdot c$ then
$$R(x) = cR_1(x) \in \mathbb{Z}[x].$$

Putting $x = -2$, since $n$ is odd, we get
$$Q(-2) = (-14) \mid f_n(-2) = -(5^n + 1).$$
Note that $5^6 \equiv 1 \pmod 6$ hence we can check that the above condition is equivalent to $n = 3k$ where $k$ is an odd natural number. On the other hand, if $n = 3k$ where $k$ is odd, we have
$$9Q(x) = (x+1)^3 + (2x-1)^3 \mid f_n(x).$$
In conclusion, the answer is $n = 6p + 3$ where $p$ is a non-negative integer. $\square$