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

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.

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

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.

• Thanks for a straightforward proof of my conjecture – J. W. Tanner Nov 19 '19 at 12:08
• You could also say two consecutive Fibonacci numbers can’t both be even, or otherwise all the Fibonacci numbers would be even, and they’re not – J. W. Tanner Nov 19 '19 at 13:20

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