Fibonacci addition law $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$ Question: Let $F_n$ the sequence of Fibonacci numbers, given by $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Show for $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$
My (very limited) attempt so far: after creating a small list of the values $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, F_9=34, F_{10}=55$ i can see that yes it does seem to work for instance $F_{6+3}=F_5 F_3 +F_6 F_4 = 10 +24 = 34 = F_9$. However, I really don't know where to begin as showing that this must hold in general terms. Should I be looking to use limits? Or perhaps induction? What is the best way to solve this?
 A: Try proving this statement:
Claim: If $f(n) = f(n-1)+f(n-2)$, then $f(n) =  F_n f_1 + F_{n-1} f_0$.
Now "fix" $m$ and think of $F_{n+m}$ as a linear recurrence in $n$ with initial conditions $F_{m+1}$ and $F_m$.
Then your claim will follow.
By the way, there is a short and clean proof of Claim, but you should know it uses the fact $F_{-1} = 1$.(Something you can easily verify if you did not already know).
A: There are several good answers already, but I thought I would add the following derivation because it is one of the few uses I know for the sum property of permanents; namely,
If $A$, $B$, and $C$ are matrices with identical entries except that one row (column) of $C$, say the $k^{th}$, is the sum of the $k^{th}$ rows (columns) of $A$ and $B$, then $\text{ per } A + \text{ per } B = \text{per } C$.
Start with the matrices $\begin{bmatrix} F_n & F_{n-1} \\ F_0 & F_1 \end{bmatrix}$ and $\begin{bmatrix} F_n & F_{n-1} \\ F_1 & F_2 \end{bmatrix}$.  Since $F_0 = 0$ and $F_1 = F_2 = 1$, they have permanents $F_n$ and $F_n + F_{n-1} = F_{n+1}$, respectively.  Applying the Fibonacci recurrence and the permanent sum property,  we have $\text{ per } \begin{bmatrix} F_n & F_{n-1} \\ F_2 & F_3 \end{bmatrix} = F_{n+2}$.  By continuing to construct new matrices whose second rows are the sums of the second rows of the previous two matrices, this process continues until we have $F_n F_{m+1} + F_{n-1}F_m = \text{ per} \begin{bmatrix} F_n & F_{n-1} \\ F_m & F_{m+1} \end{bmatrix} = F_{n+m}.$
For more on this approach (but with determinants), see this paper I wrote a few years ago: "Fibonacci Identities via the Determinant Sum Property," The College Mathematics Journal, 37 (4): 286-289, 2006. 
A: These can almost always be solved by induction. (In general sequences that are defined by recursion go often well together with induction.)
For this formula we can do the following: Induct on $m$. If $m=1$, then
$F_{n+m} = F_{n}F_{m-1} + F_{n-1}F_m = F_{n}F_{0} + F_{n-1}F_1 = F_n + F_{n-1} = F_{n+1}$.
Suppose then that the result holds for $m$ and smaller. Now
$$F_{n+m+1} = F_{n+m} + F_{n+m-1} = F_{n}F_{m-1} + F_{n-1}F_m + F_{n}F_{m-2} + F_{n-1}F_{m-1}$$
$$= F_{n}(F_{m-1} + F_{m-2}) + F_{n-1}(F_m + F_{m-1}) = F_{n}F_{m} + F_{n-1}F_{m+1}.$$
A: One simple way is to use the formula for the $n^{th}$ Fibonacci number, viz, 
$F_n = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$ where $\phi$ is the golden ratio. 
$\phi = \frac{1 + \sqrt{5}}{2}$.
Or another equally simple way is to use induction on $n$ and then on $m$ or just using induction on one of these might turn out to suffice.
It will be interesting to see a direct proof...
A: With Fibonacci numbers usually there are multiple ways of proving identities.
One way (which is one of my favourites) to prove your identity is the following:
Consider the following problem:
A person climbs up $\displaystyle n$ steps, by taking either one step, or two steps at a time.
The total number of ways the person can climb up all the $\displaystyle n$ steps is $\displaystyle F_{n+1}$ (Why?)
Now consider climbing $\displaystyle m+n-1$ steps and split into the cases when the person lands on step $\displaystyle n$ and the cases when the person lands on step $\displaystyle n-1$ and takes two steps at that point (and so does not land on step $\displaystyle n$ in those cases). These two cases cover all possibilities, and so we have:
$$\displaystyle F_{m+n} = F_{n+1}F_{m} + F_{n}F_{m-1}$$
A: If pressed, I'd nuke with Binet's formula myself, but here's another
approach. By an easy induction, if
$$A=\pmatrix{0&1\\\\ 1&1}$$
then
$$A^n=\pmatrix{F_{n-1}&F_n\\\\ F_n&F_{n+1}}.$$
Comparing the top right entry in the equation $A^m A^n=A^{m+n}$
gives
$$F_{m-1}F_n+F_m F_{n+1}=F_{m+n}.$$
A: Hint $\  $ If we put the Fibonacci recurrence into matrix form then the result is obvious, viz.
$$ M^n\ :=\ \left[\begin{array}{rr} 
\!\!1 & 1 \\\
\!\!1 & 0 \end{array}\right]^{\large n} 
=\, \left[\begin{array}{cc}
F_{n+1} &\!\! F_n \\\
F_n &\!\! F_{n-1} \end{array}\right] $$
Now comparing the entries of  $\ M^{n+m} = M^n \ M^m\,$ immediately yields the Fibonacci addition law.
Remark $\ M$ is the shift operator, i.e.  $\,(F_{n−1},F_n)M^t = (F_n,F_{n+1}).\,$  The same idea works for any linear recurrence.
A: Fix $m \in \mathbb{N}$. We shall use induction on $n$. For $n=1$, the RHS of the equation becomes $$F_{m-1}F_1 + F_mF_2 = F_{m-1} + F_{m}$$, which is equal to $F_{m+1}$. When $n=2$, the equation is also true.( I hope you can prove this!).
Now assume, that the result is true for $k=3,4, \cdots , n$. We want to show that the result is true for $k=n+1$. $$ \text{For} \ k=n-1 \ \text{we have} \quad F_{m+n-1} = F_{m-1}F_{n-1} + F_mF_n$$ and $$ \text{For} \ k = n \ \text{we have} \quad F_{m+n}=F_{m-1}F_{n} + F_{m}F_{n+1}$$ Adding both the sides you will get $$F_{m+n-1} + F_{m+n} = F_{m+n-1} = F_{m-1}F_{n+1} + F_{m}F_{n+2}$$
Oh, i reversed the notations. This is for proving $$F_{m+n} = F_{m-1}F_{n} + F_{m}F_{n+1}$$
