Is it true that $5^k \mid f(5^k)$?

Question

I guess if it is true that $5^k \mid f(5^k)$, where $f(n)$ denotes the $n$-th Fibonacci's number. I have tried to prove it by induction on $k$, but nothing. Have you got any ideas?

Answer 1

It is true. We have $F_{5} = 5.$ If we write $\sqrt{5}F_{n} = \alpha^{n}-\beta^{n}$ where $\alpha$ and $\beta$ are the roots of $x^{2}-x-1$ and $\alpha > \beta,$ then it follows by induction that $\alpha^{5^{k}}- \beta^{5^{k}} = \sqrt{5}5^{k} c_{k}$ for some integer $c_{k},$ though the way I see this requires working in the ring of algebraic integers $\mathbb{Z}[\omega],$ where $\omega = e^{\frac{2 \pi i}{5}}.$ You seem to want to find your own proof, so I don't give all the details. The key point is that $u^{5} -v^{5} = (u-v) \prod_{i=1}^{4}(u - \omega^{i}v)$ and that $\prod_{i=1}^{4} (1-\omega^{i}) = 5.$

Answer 2

Yes, the statement is correct, provided the Fibonacci sequence is initialized with $f(0)=0$ and $f(1)=1$. That is, $f(n)$ is divisible by $5^k$ if and only if $n$ is divisible by $5^k$.

Hint: Use the explicit formula for the $n$th term, namely:

$$f(n)=\frac{\binom n1+5\binom n3+5^2\binom n5+5^3\binom n7+\cdots}{2^{n-1}}.$$

This formula for $f(n)$ can be derived by applying the binomial theorem to the formula

$$f(n)=\frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{\sqrt5\cdot2^n}.$$

Answer 3

Hint $\ $ It is very easy using the matrix representation of fibonacci numbers. Then the inductive proof amounts simply to lifting the exponent $\,\color{#0a0}{5^k\mapsto 5^{k+1}}\,$ using the Binomial Theorem, e.g.

$$\begin{eqnarray} &&\left[\begin{array}{rr}f_6&f_5\\f_5&f_4\end{array}\right] &=& \left[\begin{array}{rr}8 &5\\5&3\end{array}\right] &=&\, 3I + \color{#0a0}5A\\ \Rightarrow\, &&\left[\begin{array}{rr}f_{26}\!\!&\!\!f_{25}\\f_{25}\!\!&\!\!f_{24}\end{array}\right] &=& \left[\begin{array}{rr}8 &5\\5&3\end{array}\right]^{\large \color{#c00}5} \!\!&=& (3I + 5A)^{\large \color{#c00}5}\! =\, 3^{\large \color{#c00}5} I + {\color{#c00}5}(5A)(\cdots) =\, 3^5 I + \color{#0a0}{5^2} B\end{eqnarray}$$