Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

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

share|cite|improve this question
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
@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
up vote 12 down vote accepted

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

share|cite|improve this answer
Thanks, Zander. I knew there had to be a reason. By the way, brilliant approach! – Tito Piezas III Jun 25 '12 at 18:44

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.