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$
    – naslundx
    Aug 19 '16 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$
    – Cauchy
    Aug 19 '16 at 9:11
  • $\begingroup$ Note that you use a non-standard numbering for the $F_n!$ $\endgroup$ Aug 19 '16 at 9:35
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$
    – Cauchy
    Aug 19 '16 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$

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.