I am trying to prove Lemma 2.3.2 in Tao's analysis text: that for any two natural number, $n$ and $m$, we have $n \times m = m \times n$. I only have the properties of the natural numbers and addition to work with, along with Tao's definition of multiplication. I have been able to piece together most of the proof, but am struggling with the inductive step.
Proof. Induct on $m$, holding $n$ constant.
Base Case: ($m = 0$) When $m = 0$, we need to prove $n \times 0 = 0 \times n$. The RHS is $0$ by the definition of multiplication. To show the LHS is $0$, we induct on $n$. When $n = 0$, we have $0 \times 0 = 0$ by the definition of multiplication. Our inductive hypothesis is that $n \times 0 = 0$, and need to show that $n++ \times 0 = 0$. By the definition of multiplication, $n++ \times 0 = (n \times 0) + 0$. Using the inductive hypothesis and the properties of addition, we then have $(n \times 0) + 0 = 0 + 0 = 0$. Thus, our LHS is also $0$.
Induction Hypothesis: Assume $n \times m = m \times n$.
Induction Step: We must show that $n \times (m++) = (m++) \times n$.
I am able to manipulate the right-hand side, but it doesn't seem I am able to do much to the left-hand side.
We have:
\begin{align*}
(m++) \times n & = (m \times n) + n & & \text{Definition of multiplication} \\
& = (n \times m) + n & & \text{Inductive hypothesis} \\
& = (n++) \times m & & \text{Definition of multiplication}
\end{align*}
It doesn't seem I can do anything directly to the LHS without commutativity. My strategy was to manipulate the above into the LHS, but I can't think of where to go next.
Any help would be greatly appreciated.
Best Answer
Perhaps we will learn something from showing $1\times n=n\times 1$? $$1\times n=0{+}{+}\times n =0\times n+n=0+n=n.$$ To show that $n\times 1=n$, we use induction: $$ 0\times 1=0$$ and $$ n{+}{+}\times 1=n\times 1+1=n+1=n+0{+}{+}=(n+0){+}{+}=n{+}{+},$$ voila!
Now to the general case. You already showed $$m{+}{+}\times n=m\times n+n=n\times m+n.$$ So what we need to show is
Claim. $n\times m{+}{+}=n\times m+n$
Proof. (By induction on $n$) For $n=0$, the claim follows from $0\times m{+}{+}=0$ and $0\times m+0=0+0=0$.
Now assume $n\times m{+}{+}=n\times m+n$; we want to show $n{+}{+}\times m{+}{+}=n{+}{+}\times m+n{+}{+}$. We have $$\begin{align}n{+}{+}\times m{+}{+}&=n\times m{+}{+}+ m{+}{+} \\&=(n\times m+n)+ m{+}{+}\\&=n\times m+(n+ m{+}{+}) \\&=n\times m+(n+ m){+}{+} \\&=n\times m+(m+n){+}{+}\\ &=n\times m+(m+n{+}{+})\\ &=(n\times m+m)+n{+}{+}\\ &=n{+}{+}\times m+n {+}{+}\end{align}$$ $\square$