Given the following proof:
Let $F_n$ be the $n$-th Fibonacci number. Prove or disprove: $5 | F_{5k}$ for all positive integers $k$.
I am confused exactly where to start. The Fibonacci numbers are defined recursively correct? So wouldn't this be something that I can prove with strong induction?
On
Just using the recurrence $F_{n+1}=F_n+F_{n-1}$ few times, you can get $$F_{5n+5}=5F_{5n+1}+3F_{5n}$$ You can use this identity to prove your claim by induction.
On
Modulo $5$ the Fibonacci sequence becomes $$ 0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1, ... $$ and from this point on repeats periodically. So we see that for indexes $5k$ we have $F_{5k}\equiv0\bmod5$.
On
If we take $F_1=F_2=1$, then we certainly have that $5|F_5=5$. Let's look at the Fibonacci numbers, reduced modulo $5$:
$F_1\equiv 1\\ F_2\equiv 1\\ F_3\equiv 2\\ F_4\equiv 3\\ F_5\equiv 0\\ F_6\equiv 3\\ F_7\equiv 3\\ F_8\equiv 1\\ F_9\equiv 4\equiv -1\\ F_{10}\equiv 0\\ F_{11}\equiv -1\\ F_{12}\equiv -1\\ F_{13}\equiv -2\\ F_{14}\equiv -3\\ F_{15}\equiv 0\\ F_{16}\equiv -3\\ F_{17}\equiv -3\\ F_{18}\equiv -1\\ F_{19}\equiv -4\equiv 1\\ F_{20}\equiv 0\\ $
After this, the pattern begins to repeat, and it appears that $F_{n+20}\equiv -F_{n+10}\equiv F_n$ for all $n$. This, together with $F_5\equiv F_{10}\equiv 0\pmod 5$ is sufficient to establish your claim.
On
You don't have to define the Fibbonacci sequence recursively
You could say:
$F_n = \frac{\phi^n + \phi'^n}{\phi - \phi'}$
where $\phi = \frac {1 + \sqrt 5}{2}$ and $\phi' = \frac {1 - \sqrt 5}{2}$
$F_{5k} = \frac{\phi^{5k} + \phi'^{5k}}{\phi - \phi'} = \frac{\phi^{5} + \phi'^{5}}{\phi - \phi'} (\phi^{5k-5} + \phi^{5k-10}\phi' + \cdots \phi'^{5k-1}) = F_5(\phi^{5k-5} + \phi^{5k-10}\phi' + \cdots \phi'^{5k-1})$
and $F_5 = 5$
More generally $k|n \implies F_k | F_n$
On
Let
\begin{eqnarray*}
A=
\begin{bmatrix}
0 &1 \\1 &1 \\
\end{bmatrix} .
\end{eqnarray*}
Then
\begin{eqnarray*}
A^n=
\begin{bmatrix}
F_{n-1} &F_n \\F_n &F_{n+1} \\
\end{bmatrix}
\end{eqnarray*}
and
\begin{eqnarray*}
A^5=
\begin{bmatrix}
3 &5 \\5 &8 \\
\end{bmatrix} .
\end{eqnarray*}
In particular \begin{eqnarray*} A^{5n}= \begin{bmatrix} F_{5n-1} &F_{5n} \\F_{5n} &F_{5n+1} \\ \end{bmatrix} . \end{eqnarray*} \begin{eqnarray*} A^{5n+5}= \begin{bmatrix} F_{5n+4} &F_{5n+5} \\F_{5n+5} &F_{5n+6} \\ \end{bmatrix} = \begin{bmatrix} . &3F_{5n}+5F_{5n+1} \\. &. \\ \end{bmatrix} . \end{eqnarray*} and thus the result follows by induction.
On
The characteristic polynomial of the sequence $\{F_n\}_{n\geq 0}$ is the minimal polynomial of $\varphi$ over $\mathbb{Q}$, namely $x^2-x-1$. It follows that the characteristic polynomial of the sequence $\{F_{5n}\}_{n\geq 0}$ is the minimal polynomial of $\varphi^5$, namely $x^2-11x-1$, and $$ F_{5k+10} = 11 F_{5k+5} + F_{5k}. $$ Since both $F_0$ and $F_5$ are multiples of $5$, the previous recurrence implies that $5\mid F_{5k}$ for any $k\in\mathbb{N}$. Actually, we can say much more: due to this version of Hensel's lifting lemma, $$ \nu_5(F_n) = \nu_5(n) $$ which can be proved through the following identity, too: $$\begin{eqnarray*} F_{5k} &=& F_k (\varphi^{4k}+\varphi^{3k}\overline{\varphi}^k+\varphi^{2k}\overline{\varphi}^{2k}+\varphi^k\overline{\varphi}^{3k}+\overline{\varphi}^{4k})\\&=&F_k\left(25 F_k^4+25F_k^2+5\right)\\&=&5F_k\underbrace{(5F_k^4+5F_k^2+1)}_{\not\equiv 0\pmod{5}}\end{eqnarray*}$$ implying $\nu_5(F_{5k})=1+\nu_5(F_k)$.
Well, $F_5=5$ and $5\mid5$, right?!
Now, suppose that $5\mid F_{5k}$. Then\begin{align}F_{5(k+1)}&=F_{5k+5}\\&=F_{5k+4}+F_{5k+3}\\&=F_{5k+3}+F_{5k+2}+F_{5k+2}+F_{5k+1}\\&=F_{5k+3}+2F_{5k+2}+F_{5k+1}\\&=F_{5k+2}+F_{5k+1}+2F_{5k+1}+2F_{5k}+F_{5k+1}\\&=3F_{5k}+5F_{5k+1}.\end{align}Since $5\mid F_{5k}$, it follows from this that $5\mid F_{5(k+1)}$.