Is there a proof for this Fibonacci relationship?

Solution 1:

HINT $\ \ $ If you change variables this Fibonacci addition law can be put in the form

$$\color{#c00}{F_{n+m} = F_nF_{m+1} + F_{n-1}F_m} $$

Expressing the Fibonacci recurrence in matrix form makes the proof of the addition law easy

$$ M^n\ :=\ \left(\begin{array}{ccc} \,1 & 1 \\\ 1 & 0 \end{array}\right)^n\ =\ \left(\begin{array}{ccc} F_{n+1} & F_n \\\ F_n & F_{n-1} \end{array}\right) $$ $$\begin{eqnarray} M^{n+m} = M^n M^m &=& \left(\begin{array}{ccc} F_{n+1} & F_n \\\ F_n & F_{n-1} \end{array}\right)\ \left(\begin{array}{ccc} F_{m+1} & F_m \\\ F_m & F_{m-1} \end{array}\right) \\ \\ \\ \Rightarrow\ \ \left(\begin{array}{ccc} F_{n+m+1} & F_{n+m} \\\ \color{#c00}{F_{n+m}} & F_{n+m-1} \end{array}\right) &=&\left(\begin{array}{ccc} F_{n+1}F_{m+1} + F_nF_m & F_{n+1}F_m + F_nF_{m-1} \\\ \color{#C00}{F_nF_{m+1} + F_{n-1}F_m} & F_{n}F_{m} + F_{n-1}F_{m-1} \end{array}\right)\end{eqnarray}$$

Solution 2:

First, I want to say that I agree with Carsten Schultz's comment: what you have is almost a proof by induction, and it could be turned into one without much trouble. But I think the proof that follows is very elegant, in the sense of revealing a deeper truth, so I'd like to present it again.

Let's call a sequence "fibonacci-like" if it satisfies the recurrence $$s_{n+2} = s_n + s_{n+1}$$ for all $n$. It's easy to see (or to show) that if $s$ and $t$ are two fibonacci-like sequences, then so is the sequence that you get by multiplying every term of $s$ or of $t$ of them by some constant, and so is the sequence you get by adding together corresponding terms of $s$ and $t$. For example, $1,1,2,3,5,8\ldots$ and $2,8,10,18,28,\ldots$ are both fibonacci-like, and so is what you get if you multiply every element of $1,1,2,3,5,8\ldots$ by 3, namely $3,3,6,9,15,24,\ldots$, and so is what you get if you add them together: $3,9,12,21,33,54,\ldots$.

Since any such sequence $s_i$ is completely determined by $s_0$ and $s_1$, we can agree to write a fibonacci-like sequence with the notation $[s_0, s_1]$, where $s_0$ and $s_1$ are the first two terms of the sequence; that tells us everything about it. Then the Fibonacci sequence itself is written $[0, 1]$, whereas $[1, 3]$ is the Lucas sequence $1,3,4,7,11,\ldots$.

Observe that in this notation, $[a_0, a_1] + [b_0, b_1] = [a_0+ b_0, a_1+b_1]$. So for example if you add the Fibonacci sequence $[0,1]$ to itself, you get $[0,2]$, which is in fact the sequence $0, 2, 2, 4, 6, 10,\ldots$ that you get from adding the Fibonacci sequence to itself termwise. Similarly, $c\cdot[a_0, a_1] = [c\cdot a_0 , c\cdot a_1]$. For example if you double every term of the Lucas sequence $[1,3] = 1,3,4,7,11,\ldots$ you get $2,6,8,14,22,\ldots$, which is exactly the sequence we are writing as $[2,6]$.

Finally, observe that $[0,1]$ is that standard Fibonacci sequence whose $i$th term is $f_i$, and $[1,0]$ is the "shifted" Fibonacci sequence, whose $i$th term is $f_{i-1}$. (Note that I am following the standard convention here that has $f_0 = 0$ and $f_1 = 1$; your $F_i$ seems to have $F_0 = 1$ and $F_1=1$, which is not the usual convention.)

Now suppose we have some fibonacci-like sequence $ s = [a, b]$. (Remember, $[a,b]$ is just shorthand for the fibonacci-like sequence $a, b, a+b, a+2b, 2a+3b, \ldots$.) We can decompose $[a,b]$ as follows: $$[a,b] =b[0,1] + a[1,0] $$ which shows that $s_i = bf_i + af_{i-1}$. Indeed if you look at a the example terms I showed above you see for example that $s_4 = 2a + 3b = af_3 + bf_4$. This identity holds for any fibonacci-like sequence:

If $s$ is a fibonacci-like sequence whose first two terms are $s_0$ and $s_1$, then $$s_i = s_0f_{i-1} + s_1f_i$$ for all $i$.

(You have to properly understand $f_{-1} = 1$ for this to work at $i=0$.)

Now consider the Fibonacci sequence shifted over $k$ places for some fixed $k$: this sequence begins $f_k, f_{k+1}, f_{k+2}, \ldots$; its $i$th term is $f_{i+k}$. Obviously it is fibonacci-like. In our notation it is represented as $[f_k, f_{k+1}]$ and by the previous paragraph it is equal to $f_k[1,0] + f_{k+1}[0,1]$, so by the previous theorem its $i$th term is equal to $f_kf_{i+1} + f_{k+1}f_i$. But it's $i$th term is also equal to $f_{i+k}$, so we have:

$$f_{i+k} = f_kf_{i-1} + f_{k+1}f_i.$$

Now put $i=x, k = n-x$ and we have your claim, except you have $F_n = f_{n+1}$, so the subscripts are a little muddled.