Fibonacci sequence terms $\le a$

Question

Let $a > 0$. I would like to know what is the largest index for the Fibonacci sequence $F_n$ such that $F_n \le a$.

My effort: $F_0 = 1$, $F_1 = 2$, $F_n = F_{n-1} + F_{n-2}$ and the explicit formula is $$F_n={(1+\sqrt5)^{n+2}-(1-\sqrt5)^{n+2} \over 2^{n+2}\sqrt5}$$

So the inequation to solve is $F_n\le a$. Can't find a way to solve this

I do know where $\phi$ = golden ratio that

$$F_n = \left\lfloor {\phi^{n+2} \over \sqrt 5} \right\rfloor$$

this gives the result easily.

but I don't want to use this formula

Answer 1

As you know, $F_n$ is an integer given by the formula $\frac{(1 + \sqrt{5})^{n+2} - (1 - \sqrt{5})^{n+2}}{2^{n+2} \sqrt{5}} = \frac{(1 + \sqrt{5})^{n+2}}{2^{n+2}\sqrt{5}} - \frac{(1 - \sqrt{5})^{n+2}}{2^{n+2} \sqrt{5}}$.

Now this second term satisfies $\left| \frac{(1 - \sqrt{5})^{n+2}}{2^{n+2} \sqrt{5}} \right| < \frac12$ for all $n$, since the first term is already smaller than $\frac12$, and the base of the exponent, $\frac{1 - \sqrt{5}}{2}$ is smaller than $1$ in absolute value.

Hence $F_n$ is the integer closest to $\frac{(1 + \sqrt{5})^{n+2}}{2^{n+2} \sqrt{5}}$, which proves the fact you did not want to use. This now makes it easy to solve your inequality $F_n \le a$ - simply take logarithms to solve for $n$.

Answer 2

From OEIS (sequence number 45), the first few terms of the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,...

You can verify the correctness of the calculations by hand.

Answer 3

Let $\phi=\frac{\sqrt5+1}{2}$. Then use formula $$\frac{\phi^{n-\frac1n}}{\sqrt5}<F_n<\frac{\phi^{n+\frac1n}}{\sqrt5}$$

Answer 4

Since $F_n$ is an increasing sequence, you can do a binary search. First, find integers $a$ and $b$ such that $F_a \leq 4000000 \leq F_b$. Then look at $F_{(a+b)/2}$. If $F_{(a+b)/2} \leq 4000000$, then you know $F_{(a+b)/2} \leq 4000000 \leq F_b$. Otherwise, $F_a \leq 4000000 \leq F_{(a+b)/2}$. Keep repeating this process until you've narrowed down the set of possible indices to just one.