MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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) $$

share|cite|improve this answer
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}$.

share|cite|improve this answer

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.

share|cite|improve this answer
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)$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.