MHB Double Induction: Proving Addition is Commutative

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Induction
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
Re: Double Induction

mathmari said:
Hey! :o

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??
 
Re: Double Induction

solakis said:
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)
 
Re: Double Induction

mathmari said:
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 :$$\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
 
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)
solakis said:
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)
 
Sorry for the delay i have problems with my computer, i will answer later
 
Re: Double Induction

mathmari said:
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 :$$\forall m[m+n=m+m]$$

mathmari said:
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??
 
Last edited:
Back
Top