Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction proof

  1. Sep 25, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that P(n,m) m+n = n+m for all m,n in natural numbers.

    2. Relevant equations

    3. The attempt at a solution
    I prove by induction.

    Base case: P(0,0) = 0+0 = 0+0.
    Inductive step: Let n be an arbitrary natural number. Suppose m+n =n+m. Adding 2 to both sides of the equation gives us m+n+2 = n+m+2.(end of proof)

    My question is if this is sufficient enough as a proof. (The instructor hinted us to show P(0,0) first. Then show P(n,0) and then proceed to P(n,m). The hint confuses me.
  2. jcsd
  3. Sep 25, 2011 #2


    Staff: Mentor

    Re: Help.

    You're OK with your base case, but you need to follow your instructor's suggestion.
    Prove by induction on n that n + 0 = 0 + n; i.e., that the statement is true for P(n, 0).
    Next, prove by induction on m that n + m = m + n.
  4. Sep 26, 2011 #3
    Re: Help.

    Would I need to show P(n+1,0) and P(0,m+1) or would P(n,0) and P(m) be sufficient? Because I know that for the inductive step we prove if P(n) then P(n+1).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook