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.
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$$
This is just a difference equation so you can just solve this using standard method and after substituting initial values in I'm sure $u_p$ will have expression of the form $p \times f(p)$ of some sort where $f(p)$ is an integer.
