Prove that if $2| U_n$ then $4| (U_{n+1}^2 -U_{n-1}^2)$

Question

I am working on the following problem:

Prove that if $2$ divides $U_n$ then $4$ divides $U_{n+1}^2 - U_{n-1}^2$

NOTE: $U_n$ denotes the Fibonacci sequence, such that $$Un = U_{n-1} + U_{n-2}$$ starting at $U_0=0,$ $U_1=1$, $U_2=1$, $U_3=2$, $U_4=3$, $U_5=5$,.......

I am not quite sure how to go about this problem. What I know is that $U_n = U_{n-1} + U_{n-2}.$ When we assume that $2|U_n$ then that means $U_n=2k$, but that does not seem to be helpful here. I also know that $U_n^2 =U_nU_n+1 -U_nU_{n-1}$, so we must show that $4| ((U_{n+1}U_{n+2} -U_{n+1}U_n)-(U_{n-1}U_n -U_{n-1}U_{n-2})).$ I am stuck with how to apply these concepts to form a proof. Is there a simpler way that I am not considering? Thanks in advance. Also, I apologize for the formatting; I am very new to the site.

Answer 1

$U_{n+1}^2-U_{n-1}^2=(U_{n+1}+U_{n-1})(U_{n+1}-U_{n-1}).$

Given $U_n$ is divisible by $2$,

can you show that $(U_{n+1}+U_{n-1})$ and $(U_{n+1}-U_{n-1})$ are each divisible by $2$

[hint: replace $U_{n+1}$ with $U_n+U_{n-1}$],

so their product is divisible by $4$?

Answer 2

Note that $\gcd(U_i,U_{i+1}) = 1$ for all $i \ge 0$. Thus, since $2 \mid U_n$, then $2 \not\mid U_{n-1}$ and $2 \not\mid U_{n+1}$, i.e., they are both odd. As $k^2 \equiv 1 \pmod 8$ for all odd integers $k$, then actually $U_{n+1}^2 - U_{n-1}^2 \equiv 0 \pmod 8$, i.e., $8$ divides $U_{n+1}^2 - U_{n-1}^2$, as J. W. Tanner's question comment states.

Answer 3

We have $U_{n+1}^2 - U_{n-1}^2 = (U_{n+1}+U_{n-1})(U_{n+1}-U_{n-1}) = (U_{n+1}+U_{n-1})U_{n}= U_{2n}$. (*)

$a_n=U_{2n}$ satisfies the recurrence $a_n = 3a_{n-1} - a_{n-2}$ (see OEIS/A001906). Thus $a_n \bmod 8$ is $$ 0,1,3,0,5,7,0,1,3,0,5,7, \dots $$ So, $8$ divides $a_n=U_{2n}=U_{n+1}^2 - U_{n-1}^2$ iff $3$ divides $n$ and this happens iff $2$ divides $U_n$.

(*) See the last paragraph of https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form