We are give Fibonacci numbers.{fi | i ∈ N}, where f0 = 0, f1 = 1, fn+2 = fn +fn+1, n∈ N. How to proof with mathematical induction that if n divides by m, then fn divides by fm? I am having trouble with thinking, what should be the transition.


marked as duplicate by anomaly, Crostul, Namaste, Bill Dubuque divisibility Dec 27 '18 at 23:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Hi & welcome to MSE. Please show us what you've tried so far & are having difficulty with. Thanks. $\endgroup$ – John Omielan Dec 27 '18 at 23:29

First prove by induction on $m$ that

$F_{m+n}=F_{m+1}F_n+F_mF_{n+1}-F_m F_n$

Then put $m=kn$ and find that if $F_n|F_{kn}$ then $F_n|F_{(k+1)n}$.

  • $\begingroup$ +1 then -1. The battle is on! $\endgroup$ – Oscar Lanzi Dec 27 '18 at 23:58

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