6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ this question is very relevant. $\endgroup$ – lulu Sep 12 '16 at 12:51
  • 1
    $\begingroup$ lol I looked at that question, but I don't understand all the whacky notation that they use. $\endgroup$ – user193203821309 Sep 12 '16 at 12:52
  • 1
    $\begingroup$ What "whacky notation"? It's only "$F_n$", which means the $n$-th Fibonacci number. $\endgroup$ – Arthur Sep 12 '16 at 12:53
  • 1
    $\begingroup$ 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). $\endgroup$ – lulu Sep 12 '16 at 12:54
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry for sounding really naive but what does the numbers in superscript and subscript mean after the 'F'? $\endgroup$ – user193203821309 Sep 12 '16 at 13:02
  • 1
    $\begingroup$ @differentialequation: $F_n$ is the $n$-th Fibonacci number and $F_n^2$ is its square. $\endgroup$ – Jack D'Aurizio Sep 12 '16 at 13:02
  • 1
    $\begingroup$ 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.) $\endgroup$ – user193203821309 Sep 12 '16 at 13:05
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.. $\endgroup$ – user193203821309 Sep 12 '16 at 13:00
  • $\begingroup$ @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. $\endgroup$ – Stefan4024 Sep 12 '16 at 13:02
2
$\begingroup$

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

$\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.