# Is there a way to show that the addition of the first n terms of the Fibonacci sequence squared gives an answer divisible by a particular number?

Is there a way to show that the addition of the first n terms of the Fibonacci sequence squared gives an answer divisible by a particular number?

• this question is very relevant. – lulu Sep 12 '16 at 12:51
• lol I looked at that question, but I don't understand all the whacky notation that they use. – user193203821309 Sep 12 '16 at 12:52
• What "whacky notation"? It's only "$F_n$", which means the $n$-th Fibonacci number. – Arthur Sep 12 '16 at 12:53
• What notation? $F_n$ just means the $n^{th}$ Fibonacci number. you can prove the desired claim by induction...no need to go through the geometric argument (though it is interesting). – lulu Sep 12 '16 at 12:54

There is no need to find an explicit formula for $\sum_{n=1}^{600}F_n^2$ (but this is doable and I'll show it in the second part of this answer). The Fibonacci sequence obeys the relation $F_{n+2}=F_{n+1}+F_{n}$ and $8$ is a Fibonacci number, hence the sequence $\{F_n\pmod{8}\}_{n\geq 1}$ has a short period and the same applies to $\{F_n^2\pmod{8}\}_{n\geq 1}$: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12\\ \hline F_n\pmod{8} & 1 & 1 & 2 & 3 & 5 & 0 & 5 & 5 & 2 & 7 & 1 & 0 \\ \hline F_n^2\pmod{8} & 1 & 1 & 4 & 1 & 1 & 0 & 1 & 1 & 4 & 1 & 1 & 0\\ \hline\end{array}$$ By direct inspection, we have that $F_{6n+1}^2+F_{6n+2}^2+F_{6n+3}^2+F_{6n+4}^2+F_{6n+5}^2+F_{6n+6}^2$ is always a multiple of $8$, hence $6\mid 600$ implies $8\mid\sum_{n=1}^{600}F_n^2$.

Now the brute-force approach. Let $\sigma=\frac{1+\sqrt{5}}{2}$ and $\bar{\sigma}=\frac{1-\sqrt{5}}{2}$.
We have $\sigma+\bar{\sigma}=1$, $\sigma\bar{\sigma}=-1$ and $$F_n = \frac{\sigma^n-\bar{\sigma}^n}{\sqrt{5}},\qquad F_n^2 = \frac{\sigma^{2n}+\bar{\sigma}^{2n}-2(-1)^n}{5}$$ hence it is enough to show that $8$ is a divisor of $L_2+L_4+\ldots+L_{1200}$, where $L_n=\sigma^{n}+\bar{\sigma}^n$ is a Lucas number. Lucas numbers obey the same recurence relation as Fibonacci numbers, hence $$L_2+L_4+\ldots+L_{1200} = L_{1201}-L_{1}$$ can be easily proved by induction and it is enough to show that $L_{1201}\equiv L_1\pmod{8}$. $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline L_n\pmod{8} & 2 & 1 & 3 & 4 & 7 & 3 & 2 & 5 & 7 & 4 & 3 & 7 & 2 & 1 \\ \hline \end{array}$$ By direct inspection, the period of the sequence $\{L_n\pmod{8}\}_{n\geq 1}$ is $12$, hence $L_{1201}\equiv L_1\pmod{8}$ as wanted.

• Sorry for sounding really naive but what does the numbers in superscript and subscript mean after the 'F'? – user193203821309 Sep 12 '16 at 13:02
• @differentialequation: $F_n$ is the $n$-th Fibonacci number and $F_n^2$ is its square. – Jack D'Aurizio Sep 12 '16 at 13:02
• Thank you so much!! This is actually a very elegantly produced solution and I can't believe I actually understand all of the notation (I'm pretty new to modular arithmetic, etc.) – user193203821309 Sep 12 '16 at 13:05

You can prove by induction that the sum of the squares of the first $6n$ terms is divisible by $8$.

First, show that this is true for $n=1$:

$\sum\limits_{m=1}^{6}F_m^2=40$

Second, assume that this is true for $n$:

$\sum\limits_{m=1}^{6n}F_m^2=8k$

Third, prove that this is true for $n+1$:

$\sum\limits_{m=1}^{6(n+1)}F_m^2=$

$\sum\limits_{m=1}^{6n+6}F_m^2=$

$\left(\color\red{\sum\limits_{m=1}^{6n}F_m^2}\right)+F_{6n+1}^2+F_{6n+2}^2+F_{6n+3}^2+F_{6n+4}^2+F_{6n+5}^2+F_{6n+6}^2=$

$\color\red{8k}+F_{6n+1}^2+F_{6n+2}^2+F_{6n+3}^2+F_{6n+4}^2+F_{6n+5}^2+F_{6n+6}^2=$

$\small8k+F_{6n+1}^2+F_{6n+2}^2+(F_{6n+1}+F_{6n+2})^2+(F_{6n+1}+2F_{6n+2})^2+(2F_{6n+1}+3F_{6n+2})^2+(3F_{6n+1}+5F_{6n+2})^2=$

$8k+16F_{6n+1}^2+40F_{6n+2}^2+48F_{6n+1}F_{6n+2}=$

$8(k+2F_{6n+1}^2+5F_{6n+2}^2+6F_{6n+1}F_{6n+2})$

Please note that the assumption is used only in the part marked red.

Use the Pisano Period for $n=8$. It's $12$, meaning that after the first 12 numbers the residues modulo $8$ start repeating. Hence it's enough to split the $600$ numbers in groups of $12$ and it's fairly easy to notice that the sum of squares of numbers of each such group is divisible by 8, by just checking the first such group.

• Hi, I actually had no idea what the 'Pisano Period' is so would you mind quickly explaining how I could apply this problem to it? I've been reading about it for a few minutes.. – user193203821309 Sep 12 '16 at 13:00
• @differentialequation The Pisano Period for some positive integer $n$ is some integers after which the Fibonacci Sequence taken modulo $n$ starts repeating. In other words the Pisano Period is the length of the period modulo $n$. It's been proven that the Fibonacci Sequence is periodic modulo any positive integer. – Stefan4024 Sep 12 '16 at 13:02

Taking squares, the period of $F_n^2$ modulo 8 is just 6. A little calculation gives (overline=repeat): $$(F_n^2)_{n\geq 1} \equiv \overline{[1,1,4,1,1,0]} \ \ {\rm mod} \ 8$$