4
$\begingroup$

Updated on Friday 15th March 2019 at 5 pm in the light of comments received over the last 24 hours.

The original question was; given the well known variation of Binet's Formula: $$F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$$

Derive an elegant expression, should one exist, for; $$F_{\log (n)} + F_{\log(n)-1}$$

Of course, $$\phi=\frac{1+\sqrt{5}}{2}$$

Wolfgang Kais has pointed out that this is going to run into technical issues with raising negative numbers to the power of $\log(n)$.

Consequently, initially at least, I've been looking instead at $$F_{f(n)} + F_{f(n)-1}$$ where the function $f$ is sufficiently well behaved to not run into such issues.

In this case,

$$ (\sqrt{5})(F_{f(n)} + F_{f(n)-1})=\phi^{f(n)}-(-\phi)^{-f(n)}+ \phi^{f(n)-1}-(-\phi)^{-(f(n)-1)}$$ Using the two equivalent facts that $$1-\phi=- \frac{1}{\phi} :or: \phi=1+\frac{1}{\phi}$$

I proceeded as follows;

$$ (\sqrt{5})(F_{f(n)} + F_{f(n)-1})=\phi^{f(n)}-\big(-\frac{1}{\phi}\big)^{f(n)}+ \phi^{f(n)} \times \phi^{-1}-\big(-\frac{1}{\phi}\big)^{(f(n)-1)}$$

$$ =\phi^{f(n)}-(1-\phi)^{f(n)}+ \frac{\phi^{f(n)}}{\phi}-\big(-\frac{1}{\phi}\big)^{f(n)} \times \big(-\frac{1}{\phi}\big)^{-1}$$

$$ =\phi^{f(n)}\big(1+\frac{1}{\phi}\big)-(1-\phi)^{f(n)}-(1-\phi)^{f(n)} \times (-\phi)$$ $$ =\phi \times \phi^{f(n)} - (1-\phi) \times (1-\phi)^{f(n)}$$

Wolfgang Kais suggested immediately starting with the Fibonacci recurrence relation $$F_m=F_{m-1}+F_{m-2}$$ from which I deduce that $$F_{f(n)}+F_{f(n)-1}=F_{f(n)+1}$$ Now, applying the variation on Binet's Formula, $$F_{f(n)+1} = \frac{\phi^{f(n)+1} - (-\phi)^{-(f(n)+1)}}{\sqrt{5}}$$

$$(\sqrt{5})(F_{f(n)+1}) = \phi \times \phi^{f(n)} - \big(-\frac{1}{\phi}\big)^{f(n)+1}$$ $$ = \phi \times \phi^{f(n)} - (1-\phi)^{f(n)+1}$$ $$ =\phi \times \phi^{f(n)} - (1-\phi) \times (1-\phi)^{f(n)}$$

which is the same result as obtained previously which, if nothing else, shows that the variation on Binet's formula satisfies the Fibonacci Recurrence relation.

I'm curious to know if $$ F_{f(n)+1} = \frac{\phi \times \phi^{f(n)}}{\sqrt{5}} - \frac{(1-\phi) \times (1-\phi)^{f(n)}}{\sqrt{5}}$$ is of any use, and is it the best that can be done ?

Possibly I've exhausted what can usefully be done with this question, as I can't see the point of introducing the $\log(n)$ function, given the technical hurdles it immediately throws up.

However, any further thoughts are most welcome.

The question originally came from a friend yesterday.

The earlier ask is here : how can i place then values = F(logn)+F(logn-1) in golden ratio Fibonacci series?\lognf\logn-1-in-golden-ratio-fibonacci-series

$\endgroup$
  • 1
    $\begingroup$ Note the same basic question was asked about $2$ hours earlier at how can i place then values = F(logn)+F(logn-1) in golden ratio Fibonacci series?. I appreciate you leaving a comment on the other question about you asking it here, but you should also mention that somewhere in this new question. Thanks. $\endgroup$ – John Omielan Mar 14 at 22:28
  • 2
    $\begingroup$ As you can't take a negative number to a non-integer power, $\log(n)$ will have to be an integer, and so $F_{\log (n)} + F_{\log(n)-1} = F_{\log(n)+1}$. $\endgroup$ – Wolfgang Kais Mar 15 at 0:28
  • 1
    $\begingroup$ @Wolfgang Kais : Of course ! And if I use that in the Binet formula I can get to $$F_{\log (n)} + F_{\log(n)-1} = \frac{ \phi \times \phi^{\log (n)}-(1-\phi) \times (1- \phi)^{\log(n)}}{\sqrt{5}}$$ which is so similar to the expression I mention in my question that I think I have a single minus sign error and so have $\phi^2$ instead of $(1 - \phi)$. I'll try to reconcile the two methods tomorrow. Thanks ! $\endgroup$ – Martin Hansen Mar 15 at 1:21
  • 1
    $\begingroup$ You can also try and use the identity $$x^{\log a}=a^{\log x}.$$ Unfortunately that requires careful interpretation of complex powers unless $a$ and $x$ are both positive real numbers. It does give you a simple estimate for the sum. $\endgroup$ – Jyrki Lahtonen Mar 15 at 8:16
  • 1
    $\begingroup$ @MartinHansen: $1-\phi$ is also negative. How will you define $(-1)^{\log 2}$? $\endgroup$ – Wolfgang Kais Mar 15 at 8:56
1
$\begingroup$

@MartinHansen Sorry i cant comment as i have reputation less than 50

$$F_{log (n)} + F_{log(n)-1} = \frac{ \phi^{logn}-(-\phi)^{-log(n)}}{\sqrt5}+\frac{ \phi^{log(n)-1}-(-\phi)^{-(log(n)-1)}}{\sqrt5}$$ $${log (n)} + F_{log(n)-1} = \frac{ \phi^{log(n)}+(\phi)^{(log(n)-1)}}{\sqrt5}+\frac{ \phi^{-log(n)}+(\phi)^{-(log(n)-1)}}{\sqrt5}$$

as in asymptotic time complexity we tends to ignore constants $${log (n)} + F_{log(n)-1} = { \phi^{log(n)}+(\phi)^{(log(n)-1)}}+{\phi^{-log(n)}+(\phi)^{-(log(n)-1)}}$$ How can i proceed further from here

$\endgroup$
  • $\begingroup$ i got the answer it was actually if i consider infinity then infinity in negative is almost negligible therefore i will get $$F_{log (n)} + F_{log(n)+1} = \frac{ \phi^{logn}}{\sqrt5}+\frac{ \phi^{log(n)+1}}{\sqrt5}$$ $$F_{log (n)} + F_{log(n)+1} = \frac{ \phi^{logn}}{\sqrt5}+\frac{ \phi*phi^{log(n)}}{\sqrt5}$$ $\endgroup$ – S.Ohanzee May 23 at 9:38

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.