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

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(2i) 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 221 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 2i-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.

-
That's doubly-exponential growth. Do you have some idea of what type of recurrence could plausibly hold? –  Charles Matthews Jul 21 '10 at 10:05

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)$$

-
I believe you can also get this formula, or something equivalent, using binary exponentiation on the matrix [[1 1][1 0]]. –  Qiaochu Yuan Jul 21 '10 at 19:24

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}$.

-

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.

-
nice! ps: please note that "formulae" is plural of "formula":-) –  Pietro Majer Jul 21 '10 at 11:23
It there a typo here? Starting with $x_0=1$ and $x_1=1$, the recursion produces $x_2=3$ (correct), $x_3=21$ (correct), and $x_4=2016$ (should be 987). –  tdnoe Jul 22 '10 at 15:58
tdnoe, thank you for your comment! It indeed was a typo. –  falagar Jul 23 '10 at 8:21

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)$.

-
This is of course the Newton-Raphson iteration for the square root of five, which can easily be seen to be the limit of L/F. –  Dror Speiser Jul 23 '10 at 10:55