0
$\begingroup$

Let $F_n$ be the Fibonacci sequence ($F_1=1, F_2=1, F_3=2, \ldots F_n$ such that $F_n = F_{n-1} + F_{n-2}$). Show that $F_n$ divides $F_{rn}$ for all $r,n \ge 1$.

I'm not sure how to show this rigorously. I feel that eventually the terms repeat and so $F_{nr} = qF_n$, where $q$ is an integer.

image

(I attached the problem in an image since I used LaTex with my intuition.) I thought about using induction but got nowhere and am completely stuck. How would I start and what would I need to show? This is for an introductory number theory class.

$\endgroup$
6
  • 1
    $\begingroup$ Forgot something? $\endgroup$ – Hagen von Eitzen Oct 5 '17 at 22:12
  • $\begingroup$ Sorry, I fixed it. $\endgroup$ – Dominated Convergence Theorem Oct 5 '17 at 22:17
  • 1
    $\begingroup$ The Fibonacci sequence: $F_n = F_{n-1} + F_{n-2}$ Now substitute $F_{n-1} = F_{n-2} + F_{n-3}$ into the previous. Keep doing it. Can you find a pattern? Derive a new formula for the sequence such that $F_n = F_k\times \text {Something} + \text {Something else}$ and then show that if $k$ divides $n, F_k$ is a factor of both terms. $\endgroup$ – Doug M Oct 5 '17 at 22:24
  • $\begingroup$ I found the equality F_n = F_{k+1} F{n-k} + F_k F{n-k-1}. The problem is if I decompose F_{k+1}, I get two terms, so I can't factor F_k from the equality stated. $\endgroup$ – Dominated Convergence Theorem Oct 5 '17 at 22:27
  • 1
    $\begingroup$ @DominatedConvergenceTheorem Please do not replace the question details with a "thanks" post. That qualifies as defacement and should never be done; doing so can get you in trouble. $\endgroup$ – user279515 Oct 4 '18 at 16:45
0
$\begingroup$

I'll prove a slightly more general result.

Suppose that $F_n\equiv 0 \bmod k$, and $F_{n+1} \equiv c \bmod k$. Then of course immediately $F_{n+2} \equiv 0{+}c$ $\equiv c \bmod k$ and thus $F_{n+i} \equiv cF_i \bmod k$ and $F_{2n+i} \equiv c^2F_i \bmod k$ etc.

In particular $F_{rn} \equiv c^{r-1} F_n$ $\equiv c^{r-1}{\cdot\,} 0$ $\equiv 0 \bmod k$.

In the specific case of this question, set $k=F_n$.

$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.