# How many Fibonacci Numbers are in the sequence

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$?

• Exactly, I am not sure what my induction hypothesis would be? – user240718 May 22 '15 at 7:36

## 1 Answer

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