Double Induction: Proving Addition is Commutative

[mathmari]

Hey!

I am looking for an example of an application of the double induction.

For that I tried to show that the addition is commutative: For $m,n\in \mathbb{N}$ it holds that $m+n=n+m$. I have done the following:

For each $n\in \mathbb{N}$ let $E_n$ be the proposition: $\forall m\in \mathbb{N}: m+n=n+m$.

Base Case:
For $n = 1$ we want to show that $\forall m\in \mathbb{N}: m+1=1+m$

• Base Case: For $m=1$ the left side is equal to $1+1=2$ and the right side is the same.
• Inductive Hypothesis: Let the proposition hold for a specific $m\in \mathbb{N}$, i.e. let$m+1=1+m$ (I.H.1)
• Inductive Step: We want to show that the proposition holds also for $m+1$, so $(m+1)+1=1+(m+1)$.
  We have the following:
  \begin{equation*}(m+1)+1 \overset{\text{ (I.H.1) }}{ = } (1+m)+1=1+m+1=1+(m+1)\end{equation*}
  Therefore the proposition holds for $m + 1$.

Inductive Hypothesis:
We suppose that the proposition holds for a specific $n\in \mathbb{N}$, i.e. let $\forall m\in \mathbb{N}: m+n=n+m$ (I.H.2) Inductive Step:
We want to show that the proposition holds also for $n+1$, so $\forall m\in \mathbb{N}: m+(n+1)=(n+1)+m$.

• Base Case: For $m=1$ the left side is equal to $1+(n+1)=1+n+1=(1+n)+1\overset{\text{ (I.H.2) }}{ = }(n+1)+1=n+1+1=n+2$ and the right side is equal to $(n+1)+1=n+1+1=n+2$.
• Inductive Hypothesis: We suppose that the proposition holds for a specific $m\in \mathbb{N}$, i.e. let $m+(n+1)=(n+1)+m$ (I.H.3)
• Inductive Step: We want to show that the proposition holds also for $m+1$, so $(m+1)+(n+1)=(n+1)+(m+1)$.
  We have the following:
  \begin{align*}(m+1)+(n+1)&=m+1+n+1 \\ & =m+(1+n)+1 \\ & \overset{\text{ (I.B.2) }}{ = }m+(n+1)+1 \\ & =m+n+1+1 \\ & =m+(n+1)+1 \\ & \overset{\text{ (I.B.3) }}{ = }(n+1)+m+1 \\ & =(n+1)+(m+1)\end{align*}
  Therefore the proposition holds for $m + 1$.

Is the way I applied the inductions correct? (Wondering)

 

[solakis1]

Re: Double Induction

Hey!

I am looking for an example of an application of the double induction.

For that I tried to show that the addition is commutative: For $m,n\in \mathbb{N}$ it holds that $m+n=n+m$. I have done the following:

For each $n\in \mathbb{N}$ let $E_n$ be the proposition: $\forall m\in \mathbb{N}: m+n=n+m$.

Base Case:
For $n = 1$ we want to show that $\forall m\in \mathbb{N}: m+1=1+m$

• Base Case: For $m=1$ the left side is equal to $1+1=2$ and the right side is the same.
• Inductive Hypothesis: Let the proposition hold for a specific $m\in \mathbb{N}$, i.e. let$m+1=1+m$ (I.H.1)
• Inductive Step: We want to show that the proposition holds also for $m+1$, so $(m+1)+1=1+(m+1)$.
  We have the following:
  \begin{equation*}(m+1)+1 \overset{\text{ (I.H.1) }}{ = } (1+m)+1=1+m+1=1+(m+1)\end{equation*}
  Therefore the proposition holds for $m + 1$.

Inductive Hypothesis:
We suppose that the proposition holds for a specific $n\in \mathbb{N}$, i.e. let $\forall m\in \mathbb{N}: m+n=n+m$ (I.H.2) Inductive Step:
We want to show that the proposition holds also for $n+1$, so $\forall m\in \mathbb{N}: m+(n+1)=(n+1)+m$.

• Base Case: For $m=1$ the left side is equal to $1+(n+1)=1+n+1=(1+n)+1\overset{\text{ (I.H.2) }}{ = }(n+1)+1=n+1+1=n+2$ and the right side is equal to $(n+1)+1=n+1+1=n+2$.
• Inductive Hypothesis: We suppose that the proposition holds for a specific $m\in \mathbb{N}$, i.e. let $m+(n+1)=(n+1)+m$ (I.H.3)
• Inductive Step: We want to show that the proposition holds also for $m+1$, so $(m+1)+(n+1)=(n+1)+(m+1)$.
  We have the following:
  \begin{align*}(m+1)+(n+1)&=m+1+n+1 \\ & =m+(1+n)+1 \\ & \overset{\text{ (I.B.2) }}{ = }m+(n+1)+1 \\ & =m+n+1+1 \\ & =m+(n+1)+1 \\ & \overset{\text{ (I.B.3) }}{ = }(n+1)+m+1 \\ & =(n+1)+(m+1)\end{align*}
  Therefore the proposition holds for $m + 1$.

Is the way I applied the inductions correct? (Wondering)

In going from (1+m)+1 to 1+m+1 and then to 1+(m+1) what axioms or theorems of the natural Nos do you apply??

 

[mathmari]

Re: Double Induction

In going from (1+m)+1 to 1+m+1 and then to 1+(m+1) what axioms or theorems of the natural Nos do you apply??

We apply here the associative property. Can we not apply that property? (Wondering)

 

[solakis1]

Re: Double Induction

We apply here the associative property. Can we not apply that property? (Wondering)

Yes that is the propery,only in going from (1+m)+1 to 1+(m+1)
The dropping of parenthesis is a combination of the associative and the commutative property of the natural Nos.

So,sofar you have proved :\(\displaystyle \forall m[m+1=1+m]\)

Now you want to prove : m+n=n+m for all n,m

Let us start by using induction on ,n while we keep m fixed

for n=1 we have m+1=1+m as proved previously.........1

Suppose now for n=k ,m+k=k+m is true..........2

If we can prove for n=k+1 , m+(k+1)=(k+1)+m is true ,we are done

Proof:

m+(k+1)=

=(m+k) +1=......by using the associative property of natural Nos

=(k+m)+1 =...............by using (2)

=k+(m+1)=.......by using the associative property and the law of equality: A=B<=>B=A

=k+(1+m)=...............by using (1)

= (k+1)+m.........by using the associative property e.t.c,e.t.c

You can repeat the whole thing by doing induction on m ,while keeping n constant

 

[mathmari]

Re: Double Induction

So, you mean that we apply the induction twice, once for $n$ when $m$ is fixed and once for $m$ when $n$ is fixed? So, is the way I applied the double induction wrong? (Wondering)

In going from (1+m)+1 to 1+m+1 and then to 1+(m+1) what axioms or theorems of the natural Nos do you apply??

Do we maybe have to write $ (1+m)+1=1+(m+1)$ instead of $ (1+m)+1 = 1+m+1 = 1+(m+1)$, or can we not use that property at all? (Wondering)

 

[solakis1]

Sorry for the delay i have problems with my computer, i will answer later

 

[solakis1]

Re: Double Induction

So, you mean that we apply the induction twice, once for $n$ when $m$ is fixed and once for $m$ when $n$ is fixed? So, is the way I applied the double induction wrong?

(Wondering)

Let us follow your procedure.

You write:

"Inductive Hypothesis:
We suppose that the proposition holds for a specific $n\in \mathbb{N}$, i.e. let $\forall m\in \mathbb{N}: m+n=n+m$ (I.H.2)"

Don't you have to prove again :\(\displaystyle \forall m[m+n=m+m]\)

Do we maybe have to write $ (1+m)+1=1+(m+1)$ instead of $ (1+m)+1 = 1+m+1 = 1+(m+1)$, or can we not use that property at all? (Wondering)

In going from (1+m)+1 to 1+(m+1) we do use associativity ,but in going from (1+m)+1 to 1+m+1 what do we use??