# Why do the Fibonacci numbers recycle these formulas?

The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$ obey the following recurrence relations,

\begin{aligned} &F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm] &F_{n-1}^3-F_{n}^3-F_{n+1}^3 = -F_{3n}\\[4mm] &F_{n}^3\;-3F_{n-1}^3-6F_{n-2}^3+3F_{n-3}^3+F_{n-4}^3 = 0\\[1.5mm] &F_{n-2}^5-3F_{n-1}^5-6F_{n}^5\;+3F_{n+1}^5+F_{n+2}^5 = 6F_{5n}\\[4mm] &F_{n}^5\;\;-8F_{n-1}^5\;-40F_{n-2}^5+60F_{n-3}^5+40F_{n-4}^5-8F_{n-5}^5-F_{n-6}^5 = 0\\ &F_{n-3}^7-8F_{n-2}^7-40F_{n-1}^7+60F_{n}^7\;\;+40F_{n+1}^7-8F_{n+2}^7-F_{n+3}^7 = -240F_{7n} \end{aligned}

and so on. Why are the coefficients on the LHS the same, even though the pairs involve different odd powers?

(A little more detail is in my blog.)

-
I suspect a few signs are wrong here and there. (especially when compared to the blog) –  picakhu May 21 '12 at 12:39
Putting the last row into the OEIS search turns up some sequences with a few references. They would be a good place to start looking for an answer. –  Peter Taylor May 21 '12 at 12:43
–  lhf May 21 '12 at 12:56
@Picakhu: You are right. When I first posted here, I changed the subscripts without changing the signs. I've now reverted the subscripts back to be consistent with the blog. Peter: Thanks, whatever will we do without the OEIS? lhf: That second paper is very intriguing. Too bad I can't access it. –  Tito Piezas III May 21 '12 at 13:52
These recurrences might be special cases of $q$-calculus identities. (To see why I would guess this, plug Binet's formula into the Fibonomial coefficients and rewrite in terms of the Gaussian binomial and golden ratio.) –  anon May 21 '12 at 18:19
show 1 more comment

Let $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}=-\phi^{-1}$. Then $\sqrt{5}F_n=\phi^n-\psi^n$. \begin{align} F_n^k & = 5^{-k/2}(\phi^n-\psi^n)^k\\ & = 5^{-k/2}\sum_{j=0}^k\binom{k}{j}\phi^{n(k-j)}(-\psi^n)^j \\ & = 5^{-k/2}\sum_{j=0}^k\binom{k}{j}(-1)^{j(n+1)}\phi^{n(k-2j)} \end{align} and \begin{align} F_n^{k+2} & = 5^{-(k+2)/2}(\phi^n-\psi^n)^{k+2}\\ & = 5^{-(k+2)/2}\sum_{j=0}^{k+2}\binom{k+2}{j}(-1)^{j(n+1)}\phi^{n(k+2-2j)} \\ & = 5^{-(k+2)/2}\left(\phi^{n(k+2)}+\sum_{j=1}^{k+1}\binom{k+2}{j}(-1)^{j(n+1)}\phi^{n(k+2-2j)}+(-1)^{k+2}\psi^{n(k+2)}\right) \end{align} When $k$ is odd we can rewrite the above as \begin{align} F_n^{k+2} - 5^{-(k+1)/2}F_{n(k+2)} & = 5^{-(k+2)/2}\sum_{j=0}^{k}\binom{k+2}{j+1}(-1)^{(j+1)(n+1)}\phi^{n(k-2j)} \end{align}
Then consider the generating function \begin{align} f(x) & = \sum_{n=0}^\infty F_n^kx^n \\ & = 5^{-k/2}\sum_{n=0}^\infty\sum_{j=0}^k\binom kj (-1)^j((-1)^j\phi^{k-2j})^nx^n \\ & = 5^{-k/2}\sum_{j=0}^k \binom kj \frac{(-1)^j}{1-(-1)^j\phi^{k-2j}x}\\ & = \frac{P(x)}{\prod_{j=0}^k (1-(-1)^j\phi^{k-2j}x)} \\ & = \frac{P(x)}{1+a_1x+a_2x^2+\cdots+x^k} \end{align} for some polynomial $P(x)$, which indicates that $F_n^k$ obeys the recurrence relation $F_n^k+a_1F_{n-1}^k+a_2F_{n-2}^k+\cdots+F_{n-k}^k=0$.
Now let $G_n = F_n^{k+2}-5^{-(k+1)/2}F_{n(k+2)}$ and consider the generating function for $G_n$ using the form we established above \begin{align} g(x) & = \sum_{x=0}^\infty G_n x^n \\ & = 5^{-(k+2)/2}\sum_{n=0}^\infty\sum_{j=0}^k\binom{k+2}{j+1} (-1)^{j+1}((-1)^{j+1}\phi^{k-2j})^nx^n \\ & = \frac{Q(x)}{\prod_{j=0}^k (1-(-1)^{j+1}\phi^{k-2j}x)} \\ & = \frac{Q(x)}{1+b_1x+b_2x^2+\cdots+x^k} \end{align} for some polynomial $Q(x)$. From the second last line it is clear that the roots of the polynomial in the denominator are the negatives of the roots of the denominator in the expression for $f(x)$ above, so $b_i=(-1)^ia_i$, and so $G_n$ obeys the recurrence relation $$G_{n+h}-a_1G_{n+h-1}+a_2G_{n+h-2}-\cdots+G_{n-h}=0 \\ F_{n+h}^{k+2}-a_1F_{n+h-1}^{k+2}+a_2F_{n+h-2}^{k+2}-\cdots+F_{n-h}^{k+2}=\pm 5^{-(k+1)/2}\sum_{i=-h}^{h}(-1)^ia_iF_{(k+2)(n+i)}$$ where $h=(k-1)/2$. There's a bit more work to verify that the right side is a multiple of $F_{n(k+2)}$, but this gives an answer to the question about why the coefficients are recycled. They are the coefficients of the polynomial with roots $\phi,\psi,-\phi^3,-\psi^3,\phi^5,\psi^5,\ldots$.
We can generalize further by moving four terms to the left side: $$F_n^{k+4}-5^{-(k+3)/2}\left(F_{n(k+4)}-(-1)^n(k+4)F_{n(k+2)}\right) = \\ 5^{-(k+4)/2}\sum_{j=0}^{k}\binom{k+4}{j+2}(-1)^{(j+2)(n+1)}\phi^{n(k-2j)}$$ to get additional identities like these: \begin{align} F_{n+2}^7-3F_{n+1}^7-6&F_n^7+3F_{n-1}^7+F_{n-2}^7 &= 6F_{7n}-(-1)^n\frac{42}{5}F_{5n}\\ F_{n+3}^9-8F_{n+2}^9-40F_{n+1}^9+60&F_n^9+40F_{n-1}^9-8F_{n-2}^9-F_{n-3}^9 &= 624 F_{9n}+(-1)^n 432 F_{7n}\\ \end{align}