4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for a straightforward proof of my conjecture $\endgroup$ – J. W. Tanner Nov 19 '19 at 12:08
  • $\begingroup$ 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 $\endgroup$ – J. W. Tanner Nov 19 '19 at 13:20
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.