# Showing that addition is associative and commutative using Mathematical Induction

I recently found a book left on the AMRC coffee table “Fundamental Concepts of Mathematics” by R.L. Goodstein. Inside his book Goodstein propose to use mathematical induction to show that addition is commutative.

#### ————————————————————–

We first need to define the addition of two number as satisfying the following property: $m+(n+1)=(m+n)+1$ (this is associativity with $1$ under addition). Let us refer this property as $A_0$.

#### ————————————————————–

We can first show that associativity is always true. We write $A_1$ the property $m+(n+p)=(m+n)+p$.

The proof by induction is:

1) we know $A_1$ to be true for $p=1$ as it give $A_0$

2) let us assume it exists an integers $k$ satisfying $A_1$ so that we can write $m+(n+k)=(m+n)+k$.

It follows that:

using $A_0$    $m+(n+(k+1))=m+((n+k)+1)$

using $A_0$    $m+(n+(k+1))=(m+(n+k))+1$

since $A_1$ is true for $k$    $m+(n+(k+1))=((m+n)+k)+1$

using $A_0$    $m+(n+(k+1))=(m+n)+(k+1)$

We now see that if $k$ satisfies $A_1$ then the next integer $k+1$ satisfies $A_1$. Since $A_1$  is true for $k=1$ it is true for all positive integers.

#### ————————————————————–

From here we can show commutativity with $1$. We refer to this property as $C_0$: $a+1=1+a$ for all $a$ (positive) integers.

The proof by induction is the following:

1) we know that $C_0$ is true for $a=1$, as we simply have $1+1=1+1$

2) let us assume that it exists an integer $k$ for which $C_0$ is true. Then we can write $k+1=1+k$.

Since $k$ satisfies $C_0$    $(k+1)+1=(1+k)+1$

using $A_0$    $(k+1)+1=1+(k+1)$

We now see that if $k$ satisfy $C_0$ then the next integer $k+1$ satisfy $C_0$. Since $C_0$  is true for $k=1$ it is true for all positive integers.

#### ————————————————————–

Next we can show the property $C_1$: commutativity with any integer $a+b=b+a$.

The proof by induction is:

1) we know $C_1$ is true for $b=1$ as it gives $a+1=1+a$ which simply is $C_0$ which we now know to be true.

2) let us assume that $C_1$ is true for some integer $k$ then we can write $a+k=k+a$.

It follows that

using $A_0$   $a+(k+1)=(a+k)+1$

since $C_1$ is true for $k$    $a+(k+1)=(k+a)+1$

using $A_0$    $a+(k+1)=k+(a+1)$

using $C_0$    $a+(k+1)=k+(1+a)$

using $A_1$    $a+(k+1)=(k+1)+a$

So that we see that if $k$ satisfy $C_1$ then the next integer $k+1$ satisfy $C_1$. Therefore $C_1$ is true for all integers.