I am going through some good old Fibonacci proof by induction problems that require two counters $m, n$ instead of one.
In order to prove $P(m, n)$ for all $m,n \in \mathbb{N}$, I am thinking of first proving $P(0, 0)$ and then proving that
- $P(m,n) \implies P(m + 1, n)$
- $P(m, n) \implies P(m, n + 1)$
- $P(m, n) \implies P(m + 1, n + 1)$ (EDIT: As noted by Arthur, this is unnecessary).
but am unsure if this is a correct axiom.
Isomorphically speaking, consider an integer grid. If we can show that the bottom left most tile is black, and that if any black tile implies that the tile to the top, the top-right diagonally and the right is also black, then we can show that the entire grid is black.
This is in contrast with traditional double induction which first shows using induction that the bottom row is black, and then using induction again to show that all rows are black.
Your method is valid.
We introduce $Q(m)\equiv \forall n\colon P(m,n)$. From $P(m,n)\implies P(m+1,n)$, we infer $Q(m)\implies Q(m+1)$. Indeed, assume $Q(m)$; let $n\in \Bbb N$. Then $P(m,n)$ because $Q(m)$. Then $P(m+1,n)$ because $P(m,n)\implies P(m+1,n)$. As $n$ was arbitrary, this means $Q(m+1)$. In summary, we have shown $Q(m)\implies Q(m+1)$.
Assuming that $P(0,0)$ holds, we see from $P(m,n)\implies P(m,n+1)$ that $\forall n\colon P(0,n)$ holds. This shows $Q(0)$. Hence $\forall m\colon Q(m)$ follows by induction, but that is just $\forall m\forall n\colon P(m,n)$.