Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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: oeis.org/A000045 then to compute ;) –  Eric Naslund Jun 7 '11 at 2:19
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? –  Gerry Myerson Jun 7 '11 at 5:54
3  
Seems to be a homework problem on page 49 at math.ucsd.edu/~erickson/research/pdf/fibonacci3.pdf –  Gerry Myerson Jun 7 '11 at 6:05
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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