# Fibonacci sequence and divisibility.

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}$.

• 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$). – user_194421 Jan 16 '18 at 3:34
• Something more generic: cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml – lab bhattacharjee Jan 16 '18 at 3:37
• 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. – JB071098 Jan 16 '18 at 3:38
• 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. – 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}.$
• $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}.$ – DanielWainfleet Jan 16 '18 at 11:49