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

Solution 1:

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