<s>[INST] Let $u_{n+3} = u_n + 2u_{n+1}$ . Show that $p$ divides $u_p$ for all $p$ prime number. 
Let $(u_n)$ a sequence such that $u_0 = 3$, $u_1 = 0$, $u_2 = 4$ and $u_{n+3} = u_n + 2u_{n+1}$
Show that  $p$ divides  $u_p$ for all $p$ prime number.

I'm really stuck on this exercise,
Does anyone can give me a good HINT to start ?
Thank you in advance.
 [/INST] 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$$
</s>