When I have 2 variables and 2 base cases, can I use mathematical induction multiple times to form a proof? My textbook is asking me to prove this statement about the Fibonacci numbers:
$$F_{m+n} = F_{m} F_{n+1} + F_{m-1} F_{n}, \qquad \text{given that }m \geq 1, n \geq 0.$$
TL,DR: Can I prove this by mathematical induction on m, and then on n, separately?

In more detail:
I think I'm supposed to expand this out using the closed-form equation $$F_k = \frac{\varphi^k - \hat\varphi^k}{\sqrt{5}}$$
since that's what the chapter is on, after all, but I can't help but feel that if I did the following variant on mathematical induction,


*

*Prove the base case where $m=1$ and $n=0$,

*Prove that the case of $m, n=0$ implies the case of $m+1, n=0$, and

*Prove that the case of $m=1, n$ implies the case of $m=1, n+1$.


I would still have a valid proof on my hands. I've shown that the cases can expand "outwards" in two directions, so to speak, and so they should be able to be composed together to show that the $m, n$ case implies the $m+1, n+1$ case in general.
On the other hand, I feel like there's a subtlety that makes that not a good strategy that I'm not seeing here. Since I "know" a proof exists (because this is a textbook problem), doing that without understanding whether it applies in general could be a false step.
 A: The neat way to show this is to use matricies
\begin{eqnarray*}
\begin{bmatrix}
0  &1  \\1  &1 \\
\end{bmatrix}^m =
\begin{bmatrix}
F_{m-1}  &F_m  \\F_m  &F_{m+1} \\
\end{bmatrix} .
\end{eqnarray*}
\begin{eqnarray*}
\begin{bmatrix}
0  &1  \\1  &1 \\
\end{bmatrix}^n =
\begin{bmatrix}
F_{n-1}  &F_n  \\F_n  &F_{n+1} \\
\end{bmatrix} .
\end{eqnarray*}
So
\begin{eqnarray*}
\begin{bmatrix}
F_{m+n-1}  &F_{m+n}  \\F_{m+n}  &F_{m+n+1} \\
\end{bmatrix} =\begin{bmatrix}
0  &1  \\1  &1 \\
\end{bmatrix}^{n+m} =\begin{bmatrix}
0  &1  \\1  &1 \\
\end{bmatrix}^{m} \begin{bmatrix}
0  &1  \\1  &1 \\
\end{bmatrix}^{n}  \\ \begin{bmatrix}
F_{m-1}  &F_m  \\F_m  &F_{m+1} \\
\end{bmatrix} 
\begin{bmatrix}
F_{n-1}  &F_n  \\F_n  &F_{n+1} \\
\end{bmatrix} 
=\begin{bmatrix}
.  &F_{m-1}F_n+F_m F_{n+1}  \\.  & . \\
\end{bmatrix} .
\end{eqnarray*}
A: The trick I've learned for double induction is to do your base case $m=0$ and $n=0$ and then fix $n$ to an arbitrary value (I usually start by fixing the second one), and then do induction on $m$. Then fix $m$ to an arbitrary value and do induction on $n$. Once you've done this you know that for any value of $n$ your claim holds for all $m$ and for any one value of $m$ your clam holds for all $n$. This should be sufficient to show that your claim holds for every $(m,n)$ pair.
A: Your double induction is not sufficient the way you have set it up. You end up proving only the cases with $n=0$ and arbitrary $m$, and with $m=1$ and arbitrary $n$.  
Also, while I'm not sure you really are trying to do this, but it almost sounds like you want to go from the $(m,n)$ case directly to the $(m+1,n+1)$ case, but that wouldn't be right, since now you only hit the $(1,0)$, $(2,1)$, $(3,2)$, ... cases.  Clearly you want to get to all the cases from the whole $m \times n$ 'grid', rather than just its diagonal.
Instead, what you could do is to go from the $(m,n)$ case to both the $(m,n+1)$ case and the $(m+1,n)$ case.
Another thing to think about, though, is that you are dealing with the Fibonacci numbers, and where a single variable induction involving the Fibonacci numbers involves having to have two base cases, with this kind of double induction you'll actually need all those cases with $n=0$ and arbitrary $m$, and all the cases with $m=1$ and arbitrary $n$, as your base cases, so that you can go from the $(m-1,n)$ and the $(m,n)$ case to the $(m+1,n)$ case, and from the $(m,n-1)$ and the $(m,n)$ case to the $(m,n+1)$ case. 
That is:
Suppose you have (by induction) proven the claim to be true for all the cases with $n=0$ and arbitrary $m$, and with $m=1$ and arbitrary $n$.
So now take some arbitrary $m > 1, n > 0$
Assume Inductive hypothesis:
$$F_{m+n} = F_{m} F_{n+1} + F_{m-1} F_{n}$$
and:
$$F_{m+n-1} = F_{m} F_{n} + F_{m-1} F_{n-1}$$
and:
$$F_{m-1+n} = F_{m-1} F_{n+1} + F_{m-2} F_{n}$$
First do $m,n+1$:
$$F_{m+(n+1)} =  F_{m+n-1}+ F_{m+n} \overset{Inductive Hypothesis}{=}$$
$$ F_{m} F_{n} + F_{m-1} F_{n-1} + F_{m} F_{n+1} + F_{m-1} F_{n}=$$
$$ F_{m} (F_{n} + F_{n+1}) + F_{m-1} (F_{n-1} + F_{n})=$$
$$ F_{m} F_{n+2} + F_{m-1} F_{n+1}$$
as desired.
Now do $m+1,n$:
$$F_{m+1+n} = F_{m-1+n}+ F_{m+n} = \overset{Inductive Hypothesis}{=}$$
$$F_{m-1} F_{n+1} + F_{m-2} F_{n} + F_{m} F_{n+1} + F_{m-1} F_{n}=$$
$$(F_{m-1} + F_{m}) F_{n+1} + (F_{m-2} + F_{m-1})F_{n} =$$
$$F_{m+1} F_{n+1} + F_{m}F_{n}$$
Again, as desired.
... well, ok, so that works, but it did require infinitely many base cases, which required their very own induction. Isn't there something we can do to avoid this? Yes!
Here's something you can do. Do induction on $k$, where $k=m+n$.  That is, show that the claim holds for $(1,0)$, $(1,1)$, and $(2,0)$ as your base cases, and then show that for any $k>2$: if we assume that the claim holds for all $(m,n)$ with $m+n=k-2$ and the claim also holds for all $(m,n)$ with $m+n=k-1$, then the claim also holds for all $(m,n)$ with $m+n=k$.  Now, in proving this step, you will have to account of the edge cases where $m=1$ or where $n=0$ though, but other than that you can follow the above derivations, so that would seem to be a little less work.
Finally, here is a method to prove the claim without any difficult induction at all. Suppose that you want to go up some stairs and at every step you can take either one or two stairs: in how many ways can you get up the stairs?  Well, if we say that there are $n-1$ stairs, then it turns out there are $F_n$ ways to do it (where $F_0$ is defined to $0$ and $F_1$ to $1$). Here is why: for your first step you can either go one up or two up. Now, if by inductive hypothesis there are $F_{n-1}$ ways to finish climbing the $n-2$ stairs after having taken a step of $1$ stairs, and there are $F_{n-2}$ ways to finish climbing the $n-3$ stairs after having taken a step of $2$ stairs, then it follows that there are $F_{n-1}+F_{n-2}=F_n$ ways to climb the original $n-1$ stairs, completing the inductive proof that indeed there are  $F_n$ ways to climb $n-1$ stairs if every step you take either $1$ or $2$ stairs.
OK, but that means that we can climb $m+n-1$ stairs in $F_{m+n}$ ways. But note: we can either climb the stairs and at some point having climbed exactly $m-1$ stairs, or we can climb the stairs and at some point having climbed exactly $m-2$ stairs, after which we take a step of two stairs, and continue our way: each way of climbing the stairs will be done in one of those two different ways. OK, but the first way can be done in $F_m F_{n+1}$ ways, since you can go up $m-1$ steps in $F_m$ ways and then finish the other $n$ stairs in $F_{n+1}$ ways. For the second method there are $F_{m-1}$ ways to first climb $m-2$ stairs, and then $F_n$ ways to climb the remaining $n-1$ stairs after taking a step of two stairs after that, for a total of $F_{m-1}F_n$ ways. Thus, it must be true that:
$$F_{m+n} = F_{m} F_{n+1} + F_{m-1} F_{n}$$
A: Yes, you can do such a "double induction". There are multiple different ways you can go about it, and yours looks to be valid.
However, often you don't need to do two inductions but it's merely enough to say "Fix an arbitrary $m$"  and then do an induction on $n$. Essentially you are doing an induction (on $n$) that has a parameter in it ($m$), but your proof is valid regardless of the value of $m$.
For your problem, you don't need to do the second bulleted step -- if you plug in $n = 0$ you get a true statement regardless of the value of $m$. That observation serves a your base case (for all possible values of $m \gt 0$). Now just do your third step, which is an induction on $n \rightarrow n+1$, and you're done. (BTW, I don't think you have to resort to the closed form, I think you can get away with just using the standard Fibonacci recursion formula. But I haven't actually worked it out so I'm not sure.)
A: The process below is quite revealing if you bear in mind the Fibonacci sequence 
$$\begin{array}{ccccccc}F_1&F_2&F_3&F_4&F_5&F_6&\ldots\\1&1&2&3&5&8&\ldots\end{array}$$ 
and focus on the coefficients on the right hand sides:
$$\begin{align} F_k&=1F_{k-2}+1F_{k-1}\tag{write $F_{k-1}=F_{k-3}+F_{k-2}$}\\
&=1F_{k-3}+2F_{k-2}\tag{write $F_{k-2}=F_{k-4}+F_{k-3}$}\\
&=2F_{k-4}+3F_{k-3}\tag{write $F_{k-3}=F_{k-5}+F_{k-4}$}\\
&=3F_{k-5}+5F_{k-4}\tag{write $F_{k-4}=F_{k-6}+F_{k-5}$}\\
&=5F_{k-6}+8F_{k-5}\tag{etc.}\\& \phantom{a}\vdots\end{align}$$
It is natural to conjecture:
$$F_k=c_mF_{k-m}+d_{m+1}F_{k-m+1}$$
with $c_m=F_{m-1}$ and $d_{m+1}=c_{m+1}=F_m$ so that:
$$F_{k}=F_{m-1}F_{k-m}+F_mF_{k-m+1}$$
But not only that, we can see straight away from this process how to use induction to show that the coefficients $c_m$ obey the Fibonacci recurrence. 
If we finally define $n$ as $k=n+m$ then we get your result:
$$F_{n+m}=F_{m-1}F_n+F_mF_{n+1}\tag*{}$$
