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

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

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


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,


This in turn is equivalent to


and hence to


Finally, since $n$ must be an integer, $(1)$ holds if and only if


and there are


non-negative integers $n$ satisfying $(2)$. Thus, the number of Fibonacci numbers $F_k$ satisfying $2^n<F_k\le 2^{n+1}$ is


Note that for large $n$ we have


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

| cite | improve this answer | |

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.