We know that $F_n\approx \frac {\phi^n}{\sqrt 5}$, so given $a$, the next larger Fibonacci number is $F_k$, where $k= \left \lceil\frac {\log (a\sqrt 5)}{\log \phi }\right \rceil$. Similarly the $F_m$ below $b$ is $m= \left \lfloor\frac {\log (b\sqrt 5)}{\log \phi }\right \rfloor$, then there are $m-k+1$ between $a$ and $b$. You have to think about what you want if $a$ or $b$ are themselves Fibonacci numbers.
Step 1. Since, by the Binet formula,
$$ F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\bar{\sigma}^n\right), $$
where $\sigma+\bar{\sigma}=1$ and $\sigma\bar{\sigma}=-1$, we have:
$$ F_m \mid F_{mn}, $$
since in $\mathbb{Z}[x,y]$ the polynomial $x^m-y^m$ divides the polynomial $x^{mn}-y^{mn}$.
Step 2. We can prove our statement by assuming without loss of generality that $k$ is a prime power. The Chinese theorem in conjunction with Step 1 grants that if the statement holds when $k$ is a prime power, then it holds for every integer.
Step 3. The Pisano period for the Fibonacci and Lucas sequences $\!\!\pmod{2}$ is $3$. In particular, $F_n$ (as well as $L_n$) is even iff $n$ is a multiple of $3$. Moreover,
$$ F_{2n} = F_n \cdot L_n.$$
Step 4. By assuming that $2^h\mid F_n$ we have $n=3m$ in virtue of Step 3, and:
$$ F_{2^{(d-1)h}n} = F_{2^{(d-1)h}3m} = F_{2^{(d-1)h-1}3m}L_{2^{(d-1)h-1}3m} = F_{3m}\cdot\prod_{j=0}^{(d-1)h-1}L_{3\cdot 2^j m}, $$
so:
$$ \nu_2(F_{2^{(d-1)h}n})\geq \nu_2(F_{n}) + (d-1)h \geq dh,$$
since every term in the product is even. So we just proved the statement in case that $k$ is a power of $2$.
Step 5. We assume now that $k$ is odd. Since $\frac{x^l-y^l}{x-y}=\sum_{j=0}^{l-1} x^j y^{l-1-j}$, we have:
$$\frac{F_{kn}}{F_n}=\sum_{j=0}^{k-1} \sigma^{jn}\bar{\sigma}^{(k-1-j)n}=(-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn} L_{(k-1-2j)n},$$
where $L_a = \sigma^a + \bar{\sigma}^a$. If now we use the identity:
$$ L_{2a} = \sigma^{2a}+\bar{\sigma}^{2a} = 5 F_a^2 + 2(-1)^a$$
we get:
$$\frac{F_{kn}}{F_n}= (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn}\left(5 F_{\left(\frac{k-1}{2}-j\right)n}^2+2(-1)^{\left(\frac{k-1}{2}-j\right)n}\right).$$
Since $F_n$ divides $F_{mn}$ and $k$ divides $F_{n}$, the last sum $\pmod{k}$ is just:
$$ \frac{F_{kn}}{F_n}\equiv (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}}2(-1)^{\frac{k-1}{2}n}\equiv k (-1)^{\frac{k-1}{2}n}\equiv 0\pmod{k}.$$
Hence we have that $k\mid F_n$ implies $(k F_n)\mid F_{kn}$, and our claim follows by induction.
Best Answer
Looking at the Fibonacci numbers $\bmod\ 9$ yields $$ \color{#C00000}{0,1,}1,2,3,5,8,4,3,7,1,8,\color{#0000FF}{0,8,}\dots\tag{1} $$ Since the blue terms are the negative of the red terms, we get $$ F_{n+12}\equiv-F_n\pmod{9}\tag{2} $$ Since the only Fibonacci number in the first $12$ that is $0\bmod9$ is $F_0$, we get $$ F_n\equiv0\pmod{9}\Longleftrightarrow n\equiv0\pmod{12}\tag{3} $$ Therefore, $84$ of the first $1000$ Fibonacci numbers are divisible by $9$ if you start with $F_0$, but if you start with $F_1$, only $83$ of the first $1000$ are.