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 start by defining addition

————————————————————–

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.

————————————————————–

Showing associativity for all integers

————————————————————–

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.

————————————————————–

Showing that addition with 1 is commutative

————————————————————–

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.

————————————————————–

Showing that addition is commutative for all 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s