0
$\begingroup$

Given the recurrence

$d(i+1)=xFib(2i+1)-nFib(2i)$,

where $Fib$ denotes the Fibonacci sequence (i.e. $Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2$, etc) and $n$ and $x$ are arbitrary integers, is it possible to find a closed form expression for the value of $i$, let's call it $k$, for which $d(k+1)=0$?

$\endgroup$
2
  • $\begingroup$ Who is $q$? It appears only once at the end of the question. $\endgroup$
    – Alex M.
    Commented Nov 26, 2015 at 22:57
  • $\begingroup$ Just a typo, removed it. Thanks $\endgroup$ Commented Nov 26, 2015 at 23:01

2 Answers 2

1
$\begingroup$

Yes if you use Binet's closed form formula for the nth Fibonacci number. Then you will get

$k=\frac{\log_{\phi}\frac{n+x\phi^{-1}}{n-x\phi}}{4}$

where $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio.

$\endgroup$
0
$\begingroup$

If $\phi = \dfrac {1 + \sqrt 5} 2$, then you can find a proof on Wikipedia that $Fib(n) = \dfrac {\phi ^n - (- \phi) ^{-n}} {\sqrt 5}$.

Using this formula, after a few simplifications your equation will look like $x (\phi ^{2k + 1} + \phi ^{-2k - 1}) - n(\phi ^{2k} - \phi ^{-2k}) = 0$; introducing the notation $r = \phi ^{2k}$, you can rearrange this as a 2nd degree equation: $(x \phi - n) r^2 = - \dfrac x \phi - n$, to obtain $r^2 = \dfrac {\frac x \phi + n} {n - x \phi}$. A first conclusion is that your problem has no solution if $n - x \phi \le 0$. Assuming that this does not happen, you get $\phi ^{2k} = r = \sqrt {\dfrac {\frac x \phi + n} {n - x \phi}}$, so $k = \dfrac 1 4 \log _\phi \dfrac {\frac x \phi + n} {n - x \phi}$.

(Since software libraries often implement just the natural logarithm, if you want to compute that logarithm in a program remember that $\log _x y = \dfrac {\log y} {\log x}$; you will probably obtain a decimal number, therefore you should take its integer part. In fact, how do you know that the solution to your problem is an integer number?)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .