Does there exist a pure recurrence formula with polynomial coefficients for Fibonacci(2^n)?

Question

Let F(n) be the Fibonacci sequence as defined by F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) for n>=3. I'm looking for a pure recurrence formula for the function X(i)=F(2ⁱ) whose coefficients may be polynomials in i. This is Sloane's A058635. I also would like it to be "pure" in the sense that there is no auxiliary function involved. Is such a formula known?

I attempted using Sister Celine's technique (as described in A=B) with the data up to 2²¹ without success.

My motivation is that I have a fairly complicated recurrence formula for another sequence, but I am only interested in the terms whose indices are of the form 2ⁱ-3. The existence (or non-existence) of a recursion for X(i) would be a kind of "proof of concept" as to whether or not I should explore the possibility of finding such a recursion for my sequence.

Answer 1

Consider sequence $x_n$, such $x_0=1, x_1=1, x_2=3$ and $x_{n+2}=x_{n+1}(5x_n^2+2)$ for all n>0. How it was done: it is well known, that $F_{2n}=F_n L_n$, where $L_n$ - n-th Lucas number. But we now, that $$ L_n=\phi^n+(-1/\phi)^n $$ Using Binet's formula: $$ F_n^2=\frac{1}{5}(\phi^{2n}+(-1/\phi)^{2n}-2(-1)^n)\to L_{2n}=5F_n^2+2(-1)^n $$ So we have: $$ F_{4n}=F_{2n}(5F_n^2+2(-1)^n) $$

Answer 2

Seeing already the examples of recurrences which can be derived from the explicit formula for $F_n$, I can only add there could not be any linear recurrence relation with polynomial coefficients satisfied by the sequence $u_n=F_{2^n}$. (This means that no sister, including Sister Celine, is of help.) The reason is simple: any solution $u_n$ of such a recurrence has asymptotics $$ u_n\sim C^nn^{\gamma}\cdot\left(c_0+\frac{c_1}n+\frac{c_2}{n^2}+\dots\right) \quad\text{as }n\to\infty, $$ for some constants $C,\gamma,c_0,c_1,c_2,\dots$, and this is definitely not the case of your sequence. But if you remove the linearity condition for the sequence, you can derive many other recurrences with constant coefficients, just playing with the explicit formula for $F_{2^n}$.

Answer 3

There is the following formula: $$ x_{n+2} = \frac{x_{n+1}^3}{2 x_{n}^2} + \frac{5}{2} x_n^2 x_{n+1} $$ I'm not sure if this is a pure recurrence formulae. If you need, I may provide a proof.

Answer 4

Interestingly, the recursion $u_{n+1} = (u_n + 5/u_n)/2$, with $u_0=1$, gives the fractions $Lucas(2^n)/Fibonacci(2^n)$.