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

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