Lexicographic Double Induction If I want to prove a statement that depends on two variables $P(m,n)$, I have to prove an array of possibilities, i.e,
\begin{align*}
     \begin{matrix}
          P(1,1) & P(1,2) & P(1,3) & \dots & P(1,n) & P(1,n+1)\\
          P(2,1) & P(2,2) & P(2,3) & \dots & P(2,n) & P(2,n+1)\\
          P(3,1) & P(3,2) & P(3,3) & \dots & P(3,n) & P(3,n+1)\\
          \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
          P(m,1) & P(m,2) & P(m,3) & \dots & P(m,n) & P(m,n+1)\\
          P(m+1,1) & P(m+1,2) & P(m+1,3) & \dots & P(m+1,n) & P(m+1,n+1)\\
     \end{matrix}
\end{align*}
which I can do using double induction. If I have a constraint on the variables, however, say $n\geq m$, then I'm left with the following array:
\begin{align*}
     \begin{matrix}
          P(1,1) & P(1,2) & P(1,3) & \dots & P(1,n) & P(1,n+1)\\
           & P(2,2) & P(2,3) & \dots & P(2,n) & P(2,n+1)\\
           &  & P(3,3) & \dots & P(3,n) & P(3,n+1)\\
           &  &  & \ddots & \vdots & \vdots\\
           &  &  &  & P(m,n) & P(m,n+1)\\
           &  &  &  &  & P(m+1,n+1)\\
     \end{matrix}
\end{align*}
Can I proceed with double induction lexicographically? That is, assume $P(m,n)$ is true for all $(m,n)\leq (a,b)$ (where $(m,n)\leq(a,b)$ if and only if $m<a \textrm{ or } (m=a\ \wedge\ n\leq b)$) and then try to prove $P(m+1,n+1)$ is true. Is lexicographic double induction a thing? Any help would be greatly appreciated.
 A: Imagine a directed graph, where each vertex is one of your statements $P(m, n)$ that you want to establish. Your base case(s) are particular instances that you can prove directly. Then, induction is just about following a path of arrows from some base case $P(m_0, n_0) \implies \cdots \implies P(m, n)$. This path is made up of individual steps, and these deduction(s) are the ones that you need to prove. "If you can take each step along the path, then you can get to your destination."
The usual, garden-variety induction involves a sequence of statements $P(n)$ that form a linear chain, so the only induction argument you have to make is that $P(n) \implies P(n+1)$ for each $n \geq n_0$, where the base case $P(n_0)$ is established by some other means.
In your triangular array, presumably you can prove $P(1, 1)$ in the top corner. Your lexicographic double induction is really two inductive arguments rolled up into one. (You can see this when you stare at the unpacked definition of the ordering on the array.)
Same row $(m = a \wedge n < b)$: You might as well consider the case $b = n+1$. This proceeds like the standard induction, since the row $m = a$ remains unchanged. In the directed graph, these are horizontal arrows to the right, from $(m, n)$ to $(m, n+1)$ for each $n \geq m$.
Different rows $(m < a)$: You might as well consider the case $a = m+1$, the subsequent row. Notice that there's no reference to column, so this amounts to proving that $P(m, n) \implies P(m+1, n')$ for any $n' \geq m+1$. In the directed graph picture of this proof, that's an arrow from a particular node $(m, n)$ to every node on the row below: $(m+1, m+1)$, $(m+1, m+2)$, etc. If you can construct such an argument, great! But the argument must somehow be agnostic to the second index. Here's a picture of the implications just stemming from one statement: $P(2, 5) \implies P(3, n)$. It's a lot!

The upshot: the base case(s) put you on the directed graph, and the inductive argument(s) allow you to take steps from one node to another on the graph. If together they provide a path to your destination node, then you did it!

It should be noted that there is a sparser graph (fewer edges) that would still work in your triangular array. Convince yourself that there's a path to any node beginning from the upper-left corner:

*

*Prove $P(1, 1)$ base case.

*Prove $P(m, n) \implies P(m, n+1)$ inductive step to right.

*Prove $P(m, m) \implies P(m+1, m+1)$ inductive step to down-right along diagonal.

