Proving formulas with products of Fibonacci numbers

1.9k Views Asked by At

While digging through my old notes, I stumbled upon some formulas involving multiplication of Fibonacci numbers that I discovered about 7 years ago (being fascinated with Fibonacci numbers at the time). I don't know if they are worth any attention. Anyway, first I would like to prove them, but I don't know how to do it. Here are the formulas:

$$ F_a \cdot F_b ~=~ F_{ \lfloor{{a+b} \over {2}}\rfloor } \cdot F_{ \lceil{{a+b} \over {2}}\rceil } ~-~ (-1)^a \cdot F_{ \lfloor{{b-a} \over {2}}\rfloor } \cdot F_{ \lceil{{b-a} \over {2}}\rceil } \tag{a} $$ $$ {F_n}^2 ~=~ \sum _{i=1} ^{n} F_{i-1} \cdot F_i ~+~ (n \bmod 2) \tag{b} $$ $$ 2 \cdot F_n \cdot F_{n+1} ~=~ {F_{n+1}}^2 + {F_n}^2 - {F_{n-1}}^2 ~=~ {F_{n+2}}^2 - {F_{n+1}}^2 - {F_n}^2 ~=~ {F_n}^2 + F_{2n} \tag{c} $$ $$ F_{2m+1} \cdot F_{2n} ~=~ {F_{n+m+1}}^2 - {F_{n+m}}^2 + {F_{n-m}}^2 - {F_{n-m-1}}^2 \tag{d} $$

Formula (a) can be split into the following cases: \begin{align} F_{2m} \cdot F_{2n} &= {F_{m+n}}^2 - {F_{m-n}}^2 \\ F_{2m+1} \cdot F_{2n+1} &= {F_{m+n+1}}^2 + {F_{m-n}}^2 \\ F_{2m+1} \cdot F_{2n} &= F_{m+n} \cdot F_{m+1+n} - F_{m-n} \cdot F_{m+1-n} = F_{n+m} \cdot F_{n+m+1} + F_{n-m} \cdot F_{n-m-1} \end{align}

Formula (b) has 2 cases: $$ {F_{2n}}^2 ~=~ \sum _{i=1} ^{2n} F_{i-1} \cdot F_i \\ {F_{2n+1}}^2 ~=~ \sum _{i=1} ^{2n+1} F_{i-1} \cdot F_i ~+~ 1 $$

Note that some of these formulae work with the negafibonacci sequence.

Any help will be greatly appreciated :)

1

There are 1 best solutions below

3
On

In my opinion, these are easiest to understand using the Binet formula $F_n = \frac{1}{s-t}(s^n - t^n)$, where $s,t$ are the positive and negative roots of $X^2 - X - 1 = 0$.

This reduces these equations to facts about polynomials in $s$ and $t$. For example:

$$(s^{m+n}-t^{m+n})^2 - (s^{2m} - t^{2m})(s^{2n} - t^{2n}) $$ $$ = s^{2m}t^{2n}+s^{2n}t^{2m} - 2(st)^{m+n}$$ $$ = (st)^{2n}(s^{m-n}-t^{m-n})^2$$

Since $st=1$, it follows (from division by $(s-t)^2$) that $F_{m+n}^2 -F_{2m} F_{2n} = F_{m-n}^2$. Your equations (a), (c), and (d) are easily dispatched this way, even for the "negafibonaccis".

For (b), we can use (a) to form a telescoping sum:

$$F_n^2 - F_{n-1} F_n = F_n (F_n - F_{n-1}) = F_n F_{n-2}$$ $$ = F_{n-1}^2 + (-1)^n$$ $$\implies \sum_{i=1}^n F_{i-1} F_i = \sum_{i=1}^n (F_i^2 - F_{i-1}^2 - (-1)^i) = F_n^2 + (n\bmod 2)$$