The Fibonacci sequence is defined as \begin{align} F_{0}=0, \ F_{1}=1 \end{align} and for all $n\in\mathbb{N}$ with $n\geq 2$, \begin{align} F_{n}=F_{n-2}+F_{n-1} \end{align} Show that for any positive integers $a,b$, if $a|b$, then $F_{a}|F_{b}$.

  • $\begingroup$ Do you know the general formula for Fibonacci numbers, that is, $F_n=\frac{\phi^n-\psi^n}{\sqrt5}$? ($\phi=\frac{1+\sqrt5}2$,$\psi=\frac{1-\sqrt5}2$). $\endgroup$ – user_194421 Jan 16 '18 at 3:34
  • 1
    $\begingroup$ Something more generic: cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml $\endgroup$ – lab bhattacharjee Jan 16 '18 at 3:37
  • $\begingroup$ Yes, but I don't think that it applies given my assumptions. I could be wrong. But the chapter I am dealing with is regarding divisibility. $\endgroup$ – JB071098 Jan 16 '18 at 3:38
  • $\begingroup$ First prove that $F_{m+n} = F_mF_{n+1} + F_{m-1}F_n$ and hence $F_{m+km} = F_mF_{km+1} + F_{m-1}F_{km}$. Then use induction. $\endgroup$ – PM 2Ring Jan 16 '18 at 3:45

From your previous Q asked 2 hours before this one, for $n,a \in \Bbb N$ we have $F_{(n+1)a}= F_{na}F_{a+1}+F_{na-1}F_a$ so if $F_a$ divides $F_{na}$ then $F_a$ divides $F_{(n+1)a}.$

  • $\begingroup$ $F_{2n}=F_n G_n$ where $(G_n)_n$ is called the Lucas Series: $G_0=2,$ $G_1=1,$ $G_{n+1}=G_n+G_{n-1}.$ $\endgroup$ – DanielWainfleet Jan 16 '18 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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