MHB Double Induction: Proving Addition is Commutative

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Induction
AI Thread Summary
The discussion focuses on using double induction to prove the commutativity of addition for natural numbers, specifically that for any natural numbers m and n, m + n = n + m. The user outlines their approach, detailing base cases and inductive steps for both m and n. Participants emphasize the importance of applying the associative and commutative properties correctly during the proof. There is also clarification on whether the induction process was applied correctly, with suggestions to explicitly state the hypotheses for clarity. The conversation ultimately aims to solidify understanding of double induction in mathematical proofs.
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