Suppose that I have a statement of the form: $$ P(m,n) = \begin{cases} P_1(m,n) , \ m \leq n \\ P_2(m,n), \ m \geq n \end{cases}$$
I want to show that $P(m,n)$ is true for all $n,m$ by taking an arbitrary $m$ and then using induction on $n$. Can I then just do induction on $P_1, P_2$ separetly? What is the logic behind this? Can I in general assume that $P_2$ is true when proving $P_1$ and vise versa?
On
No, you have to be quite a bit more careful than what you've shown.
We could prove this through the following induction procedure.
First, we show the base case, i.e., $$\forall m\in\mathbb Z\;\; P(m,m)$$Next, we do the inductive step, which has two parts we must prove
$$\forall m\;\forall n\leq m \;\;P_1(m,n)\to P_1(m,n-1)$$$$\forall m\;\forall n\geq m\;\;P_2(m,n)\to P_2(m,n+1)$$If these three conditions are satisfied, then $$\forall m,n\in\mathbb Z,\;\;P(m,n)$$
Your question is a little too vague to give a definitive answer. Depending on the forms of $P_1$ and $P_2$, various approaches might be the most straightforward. For instance, you may be able to fix an arbitrary $m$, then prove $P_1(m,n)$ for all $n\ge m$ first (by induction on $n$), and then prove $P_2(m,n)$ for all $n \le m$ (again by induction on $n$, and possibly using what you've just proved about $P_1$). Or you might first want to prove that $P_1(m,n)$ is true for all $m,n$ with $m\le n$ (by double induction, or induction on $m$ for fixed $n$, or vice versa), and then prove that $P_2(m,n)$ is true for all $m,n$ with $m\ge n$ (by the same or a different method). It's up to you. All such approaches have a common underlying logic: you first choose an enumeration of the pairs $(m,n)$, and then show that $P$ is true over that entire enumeration using ordinary (possibly strong) induction. The choice of enumeration is completely free... use a spiral if you like. But it has to be a single directed enumeration: you can't prove the $P_1$ cases assuming all the $P_2$ cases are true and at the same time assume all the $P_1$ cases in order to prove the $P_2$ cases.