0
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ "I don't want to use this formula" Why not? $\endgroup$ Commented Aug 19, 2016 at 9:06
  • $\begingroup$ @naslundx I don't know how to prove it. I don't like using things I have no proof for $\endgroup$ Commented Aug 19, 2016 at 9:11
  • $\begingroup$ Note that you use a non-standard numbering for the $F_n!$ $\endgroup$ Commented Aug 19, 2016 at 9:35

4 Answers 4

Reset to default
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Question updated $\endgroup$ Commented Aug 19, 2016 at 9:22
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.