2

I want to show using double inducton 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)\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\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 \\ & \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 double induction correct?

Can I use in this case the associative property $m + (n + 1) = (m + n) + 1$ ? If yes, have I applied it correctly at the last inductive step?

Mary Star
  • 13,956
  • 2
    For a basic property as this, I think you should first explicitly state the axioms that you plan to use. –  Oct 04 '17 at 13:03
  • What axioms can we use? Can we use the associative property? What other axioms do we need? @AnotherJohnDoe – Mary Star Oct 04 '17 at 13:11
  • 1
    Yes, the associative property alone seems enough –  Oct 04 '17 at 13:25
  • 1
    @MaryStar I can't imagine that you would not be provided with a set of axioms from which you are supposed to derive this (the Peano Axioms are what is typically used ... but we wouldn't know until you tell us), because otherwise you could just say: look, addition is commutative; we learned this in grade school! Put differently: in your proof you use the fact the addition is associative ... yes, we know that, but we know that just as well as we know that addition is commutative .. so if we have to prove commutation, why would we be able to assume association? – Bram28 Oct 04 '17 at 13:25
  • 1
    However, in your last $Inductive\ Step$, you have used the fact that $(a+b)+(c+d) = a+b+c+d$. Is that a given? –  Oct 04 '17 at 13:29
  • 3
    Maybe in the last step I would not write: $m+1+n+1$ that is formally meaningless, but instead: $m+(1+(n+1))=m+((n+1)+1)$ by the previous induction: $=(m+(n+1))+1=((n+1)+m)+1$ by the induction hypo: $=(n+1)+(m+1)$. – Mauro ALLEGRANZA Oct 04 '17 at 13:32
  • I was looking for an example where we can apply the double induction and I found that. It is not a given exercise and something like that. So, before I start the proof I have to suppose that the associative property holds, right? @Bram28 – Mary Star Oct 04 '17 at 13:33
  • 1
    @MauroALLEGRANZA Yes, that was my thinking too –  Oct 04 '17 at 13:33
  • 1
    @MaryStar OK, I understand! So yes, if you assume the associative property, then this would be a good proof involving double induction, though you should do those few steps as Mauro indicated to properly use association. Otherwise, good job! :) – Bram28 Oct 04 '17 at 13:34
  • So, by the associative property we get that \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 \ & \overset{\text{ (I.B.3) }}{ = }((n+1)+m)+1 \ & =(n+1)+(m+1)\end{align} right? @MauroALLEGRANZA – Mary Star Oct 04 '17 at 13:40
  • Ah ok! Do you maybe know also some other examples where we can use double induction? @Bram28 – Mary Star Oct 04 '17 at 13:41
  • 1
    @MaryStar Yes, your steps in your comment are good! For another example of double induction .... if you start with the Peano Axioms for arithmetic, I am pretty sure that you would need double induction to prove that $\forall x \forall y \forall z \ x\cdot(y + z) = (x\cdot y) + (x \cdot z)$ – Bram28 Oct 04 '17 at 14:19
  • Ah ok! Thank you! I will try to apply it also there! Do you maybe know also some examples where we can apply strong induction? I have applied that to show that each natural number can be written as a product of prime numbers. Do you know some others? @Bram28 – Mary Star Oct 04 '17 at 14:23
  • 1
    @MaryStar If you want to stay in the domain of natural numbers, the one you did is pretty much it, unless you get pretty advanced, like the proof for n=4 for Fermat's last theorem (which uses infinite descent, but infinite descent is really equivalent to strong induction). A popular one is the "It will take $n-1$ breaks to break a bar of chocolate into its $n$ squares". Or: A graph contains an Euler tour iff all vertices have an even degree. – Bram28 Oct 04 '17 at 14:32
  • Ah ok! Do we prove the inequality $1 + mn \leq(1 + m)^n$ for all natural numbers m and n by double induction? @Bram28 – Mary Star Oct 04 '17 at 18:48
  • 1
    @MaryStar No need for double induction for that one. You can prove that one by taking any $m$ and doing induction just on $n$. – Bram28 Oct 04 '17 at 19:31
  • I see! Thank you!! @Bram28 – Mary Star Oct 05 '17 at 23:10

0 Answers0