Fibonacci elegance sought for $F_{f (n)} + F_{f(n)-1}$

179 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

@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