2
$\begingroup$

I came across a result that if $p^n \mid f_m$ for some $n\geq1$ then $p^{n+1} \mid f_{pm}$. I was wondering if this is true.

  • 2
    @user6312: There is a pretty universal agreement on the indexing, specifically $F_0=0$. Wikipedia even says that $F_0=0$ is the modern convention, so it must be true. But seriously, we choose $F_0=0$ so that a large number of the divisibility properties work out nicely. Also, somewhat interesting is the fact that if you take the recurrence backwards, you get the formula $F_{-k}=(-1)^k F_k$. In any case, there are a lot of arguments. Here the conjecture survives up to $m=20$, but it is faster to use: http://oeis.org/A000045 then to compute ;)2011-06-07
  • 1
    What does "I came across a result" mean? Did you come across it in a book? did the book give a proof, or a reference? Or did you come across it just playing with numbers on your own, so you're not sure if it's true?2011-06-07
  • 3
    Seems to be a homework problem on page 49 at http://math.ucsd.edu/~erickson/research/pdf/fibonacci3.pdf2011-06-07

1 Answers 1

5

Here is one way, but it uses a pretty strong result. The Fibonacci numbers satisfy a multiplication formula, specifically: $$F_{kn}=\sum_{i=1}^{k}\binom{k}{i}F_{i}F_{n}^{i}F_{n-1}^{k-i}.$$ Combining this formula with the fact that the Fibonacci number satisfy the division property $F_k|F_{nk}$, you can see why your result follows.