0

I've been working on a coding challenge, and have determined how to perform a solution in logarithmic time; however, I'd like to solve it in constant time.

Given Binet's Formula for calculating the $n$-th Fibonacci sequence, I'd like to find the inverse to calculate when the Fibonacci sequence is equal to or less than some number.

Here is Binet's formula for a refresher:

$F_n = ((\frac{1+\sqrt5}{2})^n - (\frac{1-\sqrt5}{2}) ^n) / \sqrt5$

which can be simplified to:

$y = A^x - B^x$

$A = \frac{1+\sqrt5}{2}$, $B = \frac{1-\sqrt5}{2}$, $y = \frac{F_n}{\sqrt5}$, $x = n$

I'd like to solve for x; however I do not have the knowledge or educational experience to solve logarithms of different bases.

If I try:

$A^x = y + B^x$

$\log_A(A^x) = \log_A(y + B^x)$

$x = \log_A(y + B^x)$

which I am unsure how to solve from there. Is this problem even solvable?

DDS
  • 3,199
  • 1
  • 8
  • 31
Michael Choi
  • 139
  • 9
  • 2
    Here, it helps a lot that $\left(\frac {1-\sqrt 5}2\right)^n$ goes to $0$ very quickly. – lulu Apr 30 '19 at 20:29
  • @lulu hmm I'm not sure how that would help. If I took $\lim_{n->\infty} F_n$, then I could reduce it to $F_n = lim_{n->\infty} A^n$ but that doesn't give me meaningful information I believe. – Michael Choi Apr 30 '19 at 20:41
  • 1
    Well, suppose that term were actually $0$. Could you solve the problem then? – lulu Apr 30 '19 at 20:42
  • Yes, I could take the log of both sides. In the simplified example, if $\left(\frac {1-\sqrt 5}2\right)^n$ does go to 0, then $B^x$ is 0 in the simplified example. In that case you take $log_A$ of both sides and get $x = log_A(y)$, but that is completely ignore the B term here. Am I missing something here? – Michael Choi Apr 30 '19 at 20:46
  • @lulu Ohhhhhh I'm getting it, maybe I could use the squeeze theorem somehow. – Michael Choi Apr 30 '19 at 20:48
  • 1
    So, play with it. I think you'll see that the approximation works exactly in the vast majority of cases. In no case is the approximation off by more than $1$ (other than very small examples, I'm not sure there is a single instance in which the approximation is incorrect). – lulu Apr 30 '19 at 20:50
  • @lulu wow I really appreciate the help, figuring it out from your hint was really rewarding ha. – Michael Choi Apr 30 '19 at 20:51
  • 1
    Glad to have helped. Good luck! – lulu Apr 30 '19 at 20:52

1 Answers1

3

As no solution has yet been posted, using the hint that was provided about a month ago, we have

$$ \lim_{n \to \infty} \left( \frac{1-\sqrt{5}}{2} \right)^{n} = 0$$

and so, as $n$ increases,

$$ F_{n} \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{n} $$

So, solving the following inequality for $n$:

$$ \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{n} \leq K, $$

we get, after multiplying both sides by $\sqrt{5}$ and taking the natural log of both sides:

$$ n \ln\left( \frac{1 + \sqrt{5}}{2} \right) \leq \ln(\sqrt{5}K) $$

and therefore,

$$ n \leq \frac{\ln(\sqrt{5}K)}{\ln\left(\frac{1 + \sqrt{5}}{2} \right)} = \frac{\ln(\sqrt{5}K)}{\ln(1 + \sqrt{5}) - \ln 2};$$

So, we may take

$$ n = \left\lfloor \frac{\ln(\sqrt{5}K)}{\ln(1 + \sqrt{5}) - \ln 2} \right\rfloor.$$

$Remark:$ The RHS of Binet's equation is always $< 1$, tends to zero rapidly as a commentator pointed out, and so contributes very little (almost nothing as $n$ gets large) to the value of $F_{n}$. Therefore, we were able to pretty much ignore it for this problem.

DDS
  • 3,199
  • 1
  • 8
  • 31
  • yes, sorry I should have posted the solution after figuring it out. out of curiosity is it solvable without removing the rhs of the equation? – Michael Choi Jun 27 '19 at 16:05
  • Wikipedia (see https://math.stackexchange.com/questions/4341134/how-to-invert-binets-formula-for-fibonacci-numbers) seems to have an additional +1/2 inside the log. IIUC if your answer is correct that implies that that 1/2 is superfluous. – hkBst Dec 24 '21 at 12:40