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$
10
  • 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
    Commented Mar 14, 2019 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
    Commented Mar 15, 2019 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
    Commented Mar 15, 2019 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
    Commented Mar 15, 2019 at 8:16
  • 1
    $\begingroup$ @MartinHansen: $1-\phi$ is also negative. How will you define $(-1)^{\log 2}$? $\endgroup$
    – Wolfgang Kais
    Commented Mar 15, 2019 at 8:56

1 Answer 1

Reset to default
2
$\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$
1
  • $\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
    Commented May 23, 2019 at 9:38

You must log in to answer this question.

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