Is there a proof for this Fibonacci relationship? I was looking at the decomposition of Fibonacci numbers using the definition of $F_n = F_{n-1} + F_{n-2}$, and noted the pattern in the coefficients of the terms were Fibonacci numbers. It appears to hold, and I believe it's true, but I haven't seen a proof for it. Does one exist?
$F_n = 1F_{n-1} + 1F_{n-2}$
$F_n = 2F_{n-2} + 1F_{n-3}$
$F_n = 3F_{n-3} + 2F_{n-4}$
$F_n = 5F_{n-4} + 3F_{n-5}$
etc
This can be generalized to
$F_n = F_xF_{n-(x-1)}+F_{x-1}F_{n-x}$
 A: 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 its $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.
A: Hint $\ \ $ If we 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} \Longrightarrow \qquad\  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) \\ \\ 
\Longrightarrow\ \ \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}$$
Cassini's identity
arises by taking the determinant of the first matrix equality above
$$ (-1)^n = F_{n+1}F_{n-1} - F_n^2$$
A: Try going the other way.
$F_n = F_{n-1} + F_{n-2}$
$F_{n+1} = F_n + F_{n-1} = F_{n-1} + F_{n-1} + F_{n-2}$
$F_{n+2} = F_{n+1} + F_{n} = F_{n} + F_{n} + F_{n-1} = 2(F_{n-1}+F_{n-2})+F_{n-1}$
Etc. Hopefully the pattern becomes more "obvious" when seen this way. Then once you get to $F_{n+x}$, replace that with $F_{n}$ and replace your $F_n$ terms with $F_{n-x}$ and you should rederive your formula.
