• Support PF! Buy your school textbooks, materials and every day products Here!

Induction proof

  • Thread starter sli10126
  • Start date
  • #1
2
0

Homework Statement


Prove that P(n,m) m+n = n+m for all m,n in natural numbers.


Homework Equations





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.
 

Answers and Replies

  • #2
33,627
5,284


Homework Statement


Prove that P(n,m) m+n = n+m for all m,n in natural numbers.


Homework Equations





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.
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.
 
  • #3
2
0


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).
 

Related Threads on Induction proof

  • Last Post
Replies
6
Views
756
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
9
Views
954
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
769
  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
14
Views
2K
Top