If 3 divides $n+m$,show that $F_{n-m-1}F_n+F_{n-m}F_{n+1}$ is an even integer

Question

If $3$ divides $n+m$,show that $F_{n-m-1}F_n+F_{n-m}F_{n+1}$ is an even integer

I've no idea of initiating this.Please provide some hint

Answer 1

Wikipedia tells us that $$ F_{m} F_{n+1} + F_{m-1} F_n = F_{m+n} $$ which I shall rewrite as $$ F_{a-1} F_b + F_{a} F_{b+1} = F_{a+b} $$ Therefore, with $a=n-m$ and $b=n$, we get $$ F_{n-m-1}F_n+F_{n-m}F_{n+1} = F_{n-m+n} = F_{2n-m} $$ On the other hand, $F_n$ is even iff $n$ is a multiple of $3$, because the Fibonacci sequence mod $2$ is $0,1,1,0,1,1,0,\dots$ (starting at index $0$).

Therefore, $F_{n-m-1}F_n+F_{n-m}F_{n+1} = F_{n-m+n} = F_{2n-m}$ is even iff $2n-m$ is a multiple of $3$, which is equivalent to $n+m$ is a multiple of $3$, since $n+m=(3n)-(2n-m)$.