Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers I'm lost on where to start on this proof:
Using the fact that $A^m A^n = A^{m+n}$ , prove the identity
$F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$
I want to use induction starting with n = 1, but would I also have to make m = 1? I haven't done induction with 2 variables before.
or because of $A^m A^n = A^{m+n}$ should I setup the problem as a matrix (in that case what would the columns/rows be)? 
I tried doing it mathematically however I think my algebra is wrong so I won't post it here. Am I correct to believe that $F_{m-1} = F_m*-1$ is not the same as $2^{n+1} = 2^n*2$?
Any help would be appreciated, thanks.
 A: You can actually use induction here.  We induct on $n$ proving that the relation holds for all $m$ at each step of the way.  For $n=2$, $F_1 = F_2 =1$ and the identity $F_m+F_{m-1}=F_{m+1}$ is true for all $m$ by the definition of the Fibonacci sequence.  We now have a strong induction hypothesis that the identity holds for values up until $n$, for all $m$.  To show that it holds for $n+1$, for all $m$ we note that
$$
F_m F_{n+1} + F_{m-1} F_n = F_m(F_{n-1} + F_n) + F_{m-1}(F_{n-2} + F_{n-1}) = 
$$
$$
(F_mF_n+F_{m-1}F_{n-1}) + (F_mF_{n-1} + F_{m-1}F_{n-2}) = F_{m+n-1} + F_{m+n-2} = F_{m+n}.
$$
This completes the induction.
A: Fibonacci numbers have a matrix representation:
$$\left( \begin{smallmatrix} F_{n+1} & F_n \\ F_n & F_{n-1}\end{smallmatrix} \right) = \left( \begin{smallmatrix} 1 & 1 \\ 1 & 0 \end{smallmatrix}\right)^n$$
This is probably what you were meant to use for this problem.
A: Hint:  If $$v_{n}=\left[ \begin{array} {c} F_{n+1} \\ F_{n}\end{array}\right]$$Then:$$F_{m}F_{n}+F_{m-1}F_{n-1}=\langle v_{m-1},v_{n-1}\rangle$$where $\langle \cdot, \cdot \rangle$ is the standard inner product on $\mathbb{R}^2$.  This along with Vadim123's hint should get the job done.
