General formulae to jump Fibonacci indexes by arbitrary multiples? i.e: $TriplingFunction(F_{n}) = F_{3n}$

Question

I am familiar with what I assume are the majority of non-trivial ways to navigate / generate Fibonacci numbers (Binet's, matrix, fast doubling, polynomial etc). I have read through all of Dr. Ron Knott's pages on the subject multiple times.

What I have yet to come across are any generalized formulae to navigate Fibonacci numbers via arbitrary multiplication of their indexes. For example:

$$TriplingFunction(F_{n}) = F_{3n}$$ $TriplingFunction(F_{5}) = F_{15}$

$TriplingFunction(F_{13}) = F_{39}$

$$QuintuplingFunction(F_{n}) = F_{5n}$$ $QuintuplingFunction(F_{5}) = F_{25}$

$QuintuplingFunction(F_{13}) = F_{65}$

Do such formulae exist?

As fast-doubling is currently the fastest method to generate $F_{n}$, I suspect that the answer will be "no". Otherwise such formulae would allow you solve $F_{n}$ via its factors:

$F_{15} = QuintuplingFunction(TriplingFunction(F_{1}))$

etc.

Thank you kindly.

Answer 1

Just to state your conclusion first, the formula theoretically exist for the $n$-uple. The problem is that it gets increasingly complicated so I am not sure it can outperform the doubling method. To make sure our notations match, I mean $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$.

Then

$$ \begin{aligned} F_{3n} &= 5F_n^3 + 3(-1)^nF_n \\ F_{5n} &= 25F_n^5 + 25(-1)^nF_n^3 + 5 F_n. \end{aligned} $$

Such formulas are derived by general formulas of $F_n$.

Answer 2

Since $$F_{2n}=\frac2{\sqrt5}\sinh(2n\ln\phi)$$ We have $$F_{6n}=\frac2{\sqrt5}\sinh\left(3\sinh^{-1}\left(\frac{\sqrt5}2F_{2n}\right)\right)$$ And since $$F_{2n+1}=\frac2{\sqrt5}\cosh\left((2n+1)\ln\phi\right)$$ We get $$F_{6n+3}=\frac2{\sqrt5}\cosh\left(3\cosh^{-1}\left(\frac{\sqrt5}2F_{2n+1}\right)\right)$$ So if you know whether $n$ is even or odd you can extract $n$ from $F_n$, perform the desired transformation to it and then evaluate $F_{f(n)}$.

EDIT: Seeing Hw Chu's post we now see that projection can decide whether $n$ is even or odd for us: $$F_{3n}=\frac{1+(-1)^n}2\frac2{\sqrt5}\sinh\left(3\sinh^{-1}\left(\frac{\sqrt5}2F_{n}\right)\right)+\frac{1-(-1)^n}2\frac2{\sqrt5}\cosh\left(3\cosh^{-1}\left(\frac{\sqrt5}2F_{n}\right)\right)$$ And $$\cosh\left(3\cosh^{-1}x\right)=\frac12\left(\left(x+\sqrt{x^2-1}\right)^3+\left(x-\sqrt{x^2-1}\right)^3\right)=4x^3-3x$$ Also $$\sinh\left(3\sinh^{-1}x\right)=\frac12\left(\left(\sqrt{x^2+1}+x\right)^3-\left(\sqrt{x^2+1}-x\right)^3\right)=4x^3+3x$$ So $$\begin{align}F_{3n}&=\frac1{\sqrt5}\left(4x^3+3x+4x^3-3x\right)+\frac{(-1)^n}{\sqrt5}\left(4x^3+3x-4x^3+3x\right)\\ &=\frac8{\sqrt5}\left(\frac{\sqrt5}2F_n\right)^3+(-1)^n\frac6{\sqrt5}\frac{\sqrt5}2F_n=5F_n^3+3(-1)^nF_n\end{align}$$ EDIT: I was wondering how to figure out whether $n$ was even or odd because you need to know that to apply the multiplication formulas. It turns out that if $5F_n^2-4$ is a perfect square, then n is odd, while if $5n^2+4$ is a perfect square, then $n$ is even. If both are perfect squares, then $F_n=1$ and we don't know what $n$ is. If neither is a perfect square, then $F_n$ is not a Fibonacci number.

The recursions for the Chebyshev polynomials make it easier to derive these multiplication formulas. $$\begin{align}\cosh(n+1)\theta&=2\cosh n\theta\cosh\theta-\cosh(n-1)\theta\\ \sinh(n+1)\theta&=2\sinh n\theta\cosh\theta-\sinh(n-1)\theta\end{align}$$ Using these recurrences we can readily work out $\cosh n\theta$ and $\sinh n\theta$. Given $x=\cosh\theta$ and $y=\sinh\theta$, if we start from $x$ it means that the initial $n$ was odd so if the final $n$ was even so we want to know $\sinh n\theta$ expressed as much as possible in terms of $x$, while if the final $n$ was odd we need $\cosh n\theta$. $$\begin{array}{|r|l|l|}\hline n&\sinh n\theta &\cosh n\theta\quad\text{or}\quad\sinh n\theta\\\hline 0&1&0\\ 1&y&x\\ 2&2xy&2xy\\ 3&4y^{3}+3y&4x^{3}-3x\\ 4&8xy^{3}+4xy&8x^{3}y-4xy\\ 5&16y^{5}+20y^{3}+5y&16x^{5}-20x^{3}+5x\\ 6&32xy^{5}+32xy^{3}+6xy&32x^{5}y-32x^{3}y+6xy\\ 7&64y^{7}+112y^{5}+56y^{3}+7y&64x^{7}-112x^{5}+56x^{3}-7x\\ 8&128xy^{7}+192xy^{5}+80xy^{3}+8xy&128x^{7}y-192x^{5}y+80x^{3}y-8xy\\ 9&256y^{9}+576y^{7}+432y^{5}+120y^{3}+9y&256x^{9}-576x^{7}+432x^{5}-120x^{3}+9x\\ 10&512xy^{9}+1024xy^{7}+672xy^{5}+160xy^{3}+10xy&512x^{9}y-1024x^{7}y+672x^{5}y-160x^{3}y+10xy\\ 11&1024y^{11}+2816y^{9}+2816y^{7}+1232y^{5}+220y^{3}+11y&1024x^{11}-2816x^{9}+2816x^{7}-1232x^{5}+220x^{3}-11x\\ \hline\end{array}$$ For example if we want $F_{7n}$, first we check to see which of $5F_n^2\pm4$ was a perfect square, so now we know $(-1)^n$. If $n$ was even, then $$y=\frac{\sqrt5}2F_n,\quad x=\frac12\sqrt{5F_n^2+4}$$ And we want the $\sinh$ output. If $n$ was odd, then $$x=\frac{\sqrt5}2F_n,\quad y=\frac12\sqrt{5F_n^2-4}$$ And we want the $\cosh$ output. Putting these together with projection operators, $$\begin{align}F_{7n}&=\frac{1+(-1)^n}2\frac2{\sqrt5}\left(\frac{125\sqrt5}2F_n^7+\frac{175\sqrt5}2F_n^5+35\sqrt5F_n^3+\frac{7\sqrt5}2F_n\right)\\ &\quad+\frac{1-(-1)^n}2\frac2{\sqrt5}\left(\frac{125\sqrt5}2F_n^7-\frac{175\sqrt5}2F_n^5+35\sqrt5F_n^3-\frac{7\sqrt5}2F_n\right)\\ &=125F_n^7+70F_n^3+(-1)^n\left(175F_n^5+7F_n\right)\end{align}$$ For an even formula, we evaluate $F_{6n}$. In both cases we want the $\sinh$ output, but if $n$ was even we prefer a formula heavy in $y$, whereas if $n$ was odd we would like an $x$ type formula. Applying projection, $$\begin{align}F_{6n}&=\frac{1+(-1)^n}2\frac2{\sqrt5}\left(\frac{25\sqrt5}2F_n^5\sqrt{5F_n^2+4}+10\sqrt5F_n^3\sqrt{5F_n^2+4}+\frac{3\sqrt5}2F_n\sqrt{5F_n^2+4}\right)\\ &\quad+\frac{1-(-1)^n}2\frac2{\sqrt5}\left(\frac{25\sqrt5}2F_n^5\sqrt{5F_n^2-4}-10\sqrt5F_n^3\sqrt{5F_n^2-4}+\frac{3\sqrt5}2F_n\sqrt{5F_n^2-4}\right)\\ &=\left(25F_n^5+3F_n+20(-1)^nF_n^3\right)\sqrt{5F_n^2+4(-1)^n}\end{align}$$

Answer 3

Generalizing Hw Chu's answer, let, $$x = \sqrt5\, F_n$$ Then we get the rather familiar $k$-tuple formula,

$$\left(\frac{x+\sqrt{x^2+4\,(-1)^n}}{2}\right)^k-\left(\frac{-x+\sqrt{x^2+4\,(-1)^n}}{2}\right)^k = \sqrt5\,F_{\,k\,n}$$

For odd $k=3,5,7$, and noting $x$ as defined above, then, $$x^3+3(-1)^nx =\sqrt5\,F_{3n}$$ $$x^5+5(-1)^nx^3+5x =\sqrt5\,F_{5n}$$ $$x^7+7(-1)^nx^5+14x^3+7(-1)^nx =\sqrt5\,F_{7n}$$

and so on.