VMO

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{a{R}_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 $a{R}_1(x)Q(x)$ is $a$ hence $a$ is divisible by $b$. Denoted $a=b\cdot c$ then $$R(x)=c{R}_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(\mathrm{mod}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$