The characteristic equation for the recurrence relations $u_{n+3} - 2u_{n+1} - u_n = 0$ is
given by
$$\lambda^3 - 2\lambda - 1
= (\lambda-1)\left(\lambda-\frac{1+\sqrt{5}}{2}\right)\left(\lambda-\frac{1-\sqrt{5}}{2}\right)$$
Since the roots are all simple, the general solution for $u_n$ has the form
$$u_n = \alpha (-1)^n + \beta \left(\frac{1+\sqrt{5}}{2}\right)^n
+ \gamma \left(\frac{1-\sqrt{5}}{2}\right)^n$$
for suitably chosen constants $\alpha, \beta, \gamma$. With a little bit of algebra,
the initial conditions $u_0 = 3, u_1 = 0, u_2 = 4$ leads to $\alpha = \beta = \gamma = 1$.
Since $2 \mid u_2$, we just need to figure out what happens to $u_p$ when $p$ is an odd prime. For such an odd prime $p$,
$$\begin{align}
2^{p-1} u_p
&= -2^{p-1} + \frac12\bigg[ (1 + \sqrt{5})^p + (1-\sqrt{5})^p \bigg]\\
&= -2^{p-1} + \sum_{k=0, k\text{ even}}^p \binom{p}{k} \sqrt{5}^k\\
&= - ( 2^{p-1} - 1 ) + \sum_{\ell=1}^{\lfloor p/2\rfloor} \binom{p}{2\ell} 5^\ell
\tag{*1}
\end{align}$$
By Fermat little theorem, $p \mid 2^{p-1} -1$. Together with the fact $p \mid \binom{p}{k}$ for $1 \le k \le p-1$, we get
$$p \mid \text{RHS(*1)}\quad\implies\quad p \mid 2^{p-1} u_p\quad\implies\quad p \mid u_p$$