# 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 ?

• The sequence is tabulated at oeis.org/A099925 where it is shown to be very closely related to the Lucas sequence. You may get what you want from standard properties of Lucas numbers. – Gerry Myerson Apr 9 '14 at 13:15
• To extend on Gerry Myerson's comment: Your sequence is $u_n = L_n+(-1)^n$ (with $L_n$ the n'th Lucas number) and at mathworld.wolfram.com/LucasNumber.html you find that $L_p\equiv 1 \pmod p$ if $p$ is prime. Therefore $u_p= L_p+(-1)^p=L_p-1\equiv 0 \pmod p$ for primes $p>2$. – gammatester Apr 9 '14 at 13:22
• @gammatester: Your link gives no hint on how to prove it. Do you know anywhere that does? – TonyK Apr 9 '14 at 13:35
• @TonyK: Unfortunately not from here. But I guess from the connection to Lucas pseudo primes, there should be a proof in Crandall/Pomerance 'Prime numbers' or in one of Ribenboim's books. – gammatester Apr 9 '14 at 14:02
• @gammatester: Indeed! I have Crandall & Pomerance on my shelves, and it proves the result in section 3.6.1 "Fibonacci and Lucas psuedoprimes". In fact it proves a more general result, for a large class of recurrence relations, and the proof is too long to post here. – TonyK Apr 9 '14 at 14:16

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.

• $u_n = (-1)^n + (\frac12(1+\sqrt 5))^n + (\frac12(1-\sqrt5))^n$. How does that help us? – TonyK Apr 9 '14 at 12:58
• Clear that I was being careless. I will get back on that – Jack Yoon Apr 9 '14 at 12:59
• @TonyK binomial theorem plus $p \mid \binom{p}{k}$ for $1 \le k < p$ seems to do the magic. – achille hui Apr 9 '14 at 14:45
• @Nico, it is the same. You first figure out the characteristic equation associated with your linear recurrence relations. If all the roots of it are simple, then the solution of your linear recurrence relations is a linear combination of powers of the roots. – achille hui Apr 9 '14 at 15:01
• I think there should be an easier way; with some trick possibly or noticing some patterns; but I couldn't really seem to spot any. – Jack Yoon Apr 9 '14 at 23:19