Proof by Induction involving Two Variables

Question

I'm reading through some MIT lectures notes, located here (https://ocw.mit.edu/courses/mathematics/18-014-calculus-with-theory-fall-2010/course-notes/MIT18_014F10_course_notes.pdf) and am particularly focused on Theorem 10.

The author of the notes sought to prove that $a^n \cdot a^m = a^{n+m}$ for positive integers $n$ and $m$. It proceeds by fixing $n$ and performing "induction on $m$": starting with $m = 1$, taking a base case of, for lack of better explanation, $m = m$ (they don't quite write this, but I assume they are really assuming $P(m)$, so that $a^n \cdot a^m = a^{n+m}$), and then demonstrate $a^n \cdot a^{m+1} = a^{n+m+1}$.

The proof makes sense to me, but my question concerns how we would perform induction on two variables, especially since we need to prove this for all $n$ and all $m$, though performing induction on $m$ seems to establish this theorem for all $m$. If I'm not mistaken, the logic of this proof as well as others like it may be that, though we're fixing $n$, we're taking it to be completely arbitrary, so anything we prove for this $n$ will hold for all $n$. So, we establish that this works for all $m$, given a fixed $n$, and thus this holds for all $n$ (and, ergo, all $n$ and $m$).

Is this line of reasoning correct?

The only other proof of this kind that I've seen was an old combinatorics problem where my professor proved the theorem by "induction on $m$ relative to $n$." I wish I could find the problem, but I believe he used as a base case $m = n$, assumed it for $m = n + 1$, and then proved it for $m = n + 2$. This is admittedly very difficult to comment on since I don't have the proof on hand, though I would be very interested if anyone has any thoughts on methods of proof by induction involving two variables and whether something like this is standard.

Thanks.

Answer 1

This is a valid technique, though it’s a bit confusingly presented in that document. Consider the following:

1. $f(0,0)$ is known to be true

2. It is known that if $f(x,y)$ is true, then $f(x+1,y)$ is true

3. It is known that if $f(x,y)$ is true, then $f(x,y+1)$ is true.

We can iteratively apply the second and third line to conclude that $f(x,y)$ is true for all $(x,y)\in\mathbb N^2$. Simply use the second line to increment the $x$ value from $0$ to the desired number, and then use the third line to increment the $y$ value to the desired number.

---

There are many different ways you can define this type of “multivariate induction” based on how you wish to inductively pass through the set $\{f(x,y):x,y\in\mathbb N\}$. For example, another way would be to prove that:

1. $f(0,0)$ is true

2. If $f(x,y)$ is true for all $x,y$ such that $x+y=\ell$ for some $\ell\in \mathbb N$ then $f(x,y)$ is true for all $x,y$ such that $x+y=\ell+1$

This method looks a bit stranger, but has two benefits. Firstly, it more directly relates the proof to regular induction by exposing that the problem is actually about induction over $\ell$. Secondly, it passes through the set $\{f(x,y)\}$ in a way that is more natural for many problems. If you imagine $\{f(x,y)\}$ as a grid, this statement says that if all the points on the line of slope $-1$ and intercept $\ell$ satisfy the property, then all the points on the line of slope $-1$ and intercept $\ell+1$ do as well. This way of passing through your set is more natural in contexts line Pascal’s Triangle, where it lets you induct down the rows.

Your proof is doing this second sort of induction, just not in a particularly explicit way. The reason this is more natural in this context is that you don’t really care about if $n$ goes up by one vs if $m$ goes up by one, the only thing you care about is that the total exponent does.

---

Your argument is also valid, but it’s not an inductive argument strictly speaking. What you’re saying is:

1. It is known that, for arbitrary $x$, if $f(x,y)$ is true then $f(x,y+1)$ is true.

2. Therefore for arbitrary $x$ and all $y$, $f(x,y)$ is true.

3. Therefore for all $x,y$ $f(x,y)$ is true.

The step from 2 to 3 doesn’t use induction. It uses what is known in formal logic as the $\forall$-introduction rule, which is an axiom of first order logic. The connection between $\forall$I and the use of the word “arbitrary” is described in the Stanford Encyclopedia of Philosophy as follows:

This rule (∀I) corresponds to a common inference in mathematics. Suppose that a mathematician says “let n be a natural number” and goes on to show that n has a certain property P, without assuming anything about n (except that it is a natural number). She then reminds the reader that n is “arbitrary”, and concludes that P holds for all natural numbers. The condition that the variable v not occur in any premise is what guarantees that it is indeed “arbitrary”. It could be any object, and so anything we conclude about it holds for all objects.

The SEP article is a good source on introductory logic and the $\forall I$ rule, if you wish to learn more.