For which $k$ can $(x-1)^{k} - (x+1)^{k}$ be divided by $x$? Consider 
  $$
f_{n}(x) = (x-1)^{n} - (x+1)^{n}\,. 
$$
  For which $n$ can it be divided by $x$?


Explicitly I found that for $k = 1, 3$ $f_{n}(x)$ can not be divided by $x$, while for $n = 2$ It can.  

Next, I used the formula

$$
a^{n} - b^{n} = (a-b)(a^{n-1}+a^{n-2}b + \dots + ab^{n-2}+b^{n-1}),
$$

but I don't see the way to show something from it explicitly.
Let $p(x)=x^k$. Since $f(x)=p(x-1)-p(x+1)$ is divisible by $x$ we see that $x=0$ is zero of $f(x)$, so $p(-1)=p(1)$, so $$(-1)^k = 1^k$$ and that is only if $k$ is even.
I would say that for all even $n$. Observe that, irrespective of the value of $n$, $(x+1)^n=x^n+....+1.$ On the other hand, $(x-1)^n=x^n-....+(-1)^n.$ The last term in this polynomial will be $+1$ for even $n$, and, thus, the difference, $ (x-1)^n-(x+1)^n$ is just a polynomial of degree $n-1$ without a constant term which can always be divided by $x.$ Again, this is true only for even $n.$