0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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)}$.

$\endgroup$
4
  • $\begingroup$ Exactly what I was trying to do thank you! $\endgroup$ – APorter1031 Nov 15 '17 at 23:13
  • $\begingroup$ You stopped at 3F5k+5F5k+1 because it is of the form k + k+1, correct? $\endgroup$ – APorter1031 Nov 15 '17 at 23:49
  • $\begingroup$ @APorter1031 No, not at all. It's because $5F_{5k+1}$ is trivially a multiple of $5$ and $3F_{5k}$ is a multiple of $5$ since I am assuming that $F_{5k}$ is a multiple of $5$. My proof is a proof by induction of the assertion$$(\forall k\in\mathbb{N}):5\mid F_{5k}.$$ $\endgroup$ – José Carlos Santos Nov 15 '17 at 23:52
  • $\begingroup$ ahh, thank you for the clarification! $\endgroup$ – APorter1031 Nov 15 '17 at 23:52
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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