4
$\begingroup$

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

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

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

$\endgroup$

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.