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

  • $\begingroup$ I suspect a few signs are wrong here and there. (especially when compared to the blog) $\endgroup$ – picakhu May 21 '12 at 12:39
  • 4
    $\begingroup$ 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. $\endgroup$ – Peter Taylor May 21 '12 at 12:43
  • $\begingroup$ @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. $\endgroup$ – Tito Piezas III May 21 '12 at 13:52
  • $\begingroup$ 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.) $\endgroup$ – anon May 21 '12 at 18:19

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

  • 1
    $\begingroup$ Thanks, Zander. I knew there had to be a reason. By the way, brilliant approach! $\endgroup$ – Tito Piezas III Jun 25 '12 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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