I have $I_n = \{2^n + 1, 2^n + 2, 2^n + 3, \dots , 2^{n+1}\}$ and I am trying to prove using induction how many Fibonacci numbers are there.
First, the length of $I_n$ is $|I_n| = 2^n$ then for $F_0 = 1$ and for $F_1 = 1$ but how can I transform the Binet`s formula for my induction hypothesis and and what exactly to derive it from. The Binet formula in general: $$F_n = \frac{\phi^n -(- \phi)^n}{\sqrt{5}}$$ where $\phi = \frac{1 + \sqrt{5}}{2}$
Question How to prove with Induction over n the number of Fibonacci numbers in $I_n$?
Conceivably there is some recurrence that can be proved by induction, but I don’t at the moment see one. However, it’s possible to get an ugly exact formula without using induction.
From the Binet formula it’s not hard to deduce that
$$F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor$$
for $n\ge 0$. Thus, $F_n\le m$ if and only if
$$\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\le m\;,$$
or, equivalently,
$$\frac{\varphi^n}{\sqrt5}+\frac12<m+1\;.$$
This in turn is equivalent to
$$\varphi^n<\sqrt5\left(m+\frac12\right)$$
and hence to
$$n<\log_\varphi\sqrt5+\log_\varphi\left(m+\frac12\right)\;.\tag{1}$$
Finally, since $n$ must be an integer, $(1)$ holds if and only if
$$n<\left\lceil\log_\varphi\sqrt5+\log_\varphi\left(m+\frac12\right)\right\rceil\;,\tag{2}$$
and there are
$$\left\lceil\log_\varphi\sqrt5+\log_\varphi\left(m+\frac12\right)\right\rceil$$
non-negative integers $n$ satisfying $(2)$. Thus, the number of Fibonacci numbers $F_k$ satisfying $2^n<F_k\le 2^{n+1}$ is
$$\left\lceil\log_\varphi\sqrt5+\log_\varphi\left(2^{n+1}+\frac12\right)\right\rceil-\left\lceil\log_\varphi\sqrt5+\log_\varphi\left(2^n+\frac12\right)\right\rceil\;.\tag{3}$$
Note that for large $n$ we have
$$\sqrt5\left(2^{n+1}+\frac12\right)\approx2\cdot\sqrt5\left(2^n+\frac12\right)\;,$$
so without the ceiling function the difference in $(3)$ would be about $\log_\varphi2\approx 1.44$, and you can expect the actual value to be $1$ or $2$ depending on $n$.