What Are the Common Mistakes in Induction Proofs with Natural Numbers?

[mmmboh]

This isn't homework, just an example in the book on how induction can easily be used wrong, but I am having trouble finding exactly what the problem is with what they did, I know it's obviously not true:

Claim: If n belongs to N (the natural numbers), and p and q are natural numbers with maximum n, then p=q.
Let S be the subset of the natural numbers for which the claim is true. 1 belongs to S, since if p and q belong to N and their maximum is 1, then p=q=1. Now assume k belongs to S, and that the maximum of p and q is k+1. Then the maximum of p-1, q-1 is k. But k is in S, so p-1=q-1, thus p=q and k+1 is in S, so the assertion is true for all n in N.

Ugh this is bothering me because it should be obvious but I don't know if I'm not thinking straight today but I don't see it exactly. I know 1 is in the set, so that assertion is fine, and assuming k is in the set is your standard induction hypothesis, so the fault must be in the k+1 area, I think it's because we are already assuming that p=q, so we are basically just proving that if p-1=q-1 then p=q, but that doesn't prove the statement...I don't know this is bothering me

 

[Office_Shredder]

What kind of numbers can p-1 and q-1 be?

 

[mmmboh]

Natural, I considered that you are eliminating the possibility that p and q are 1, but I'm not sure that's the problem, because if the maximum of p and q is k+1, well k+1 is at least 2 anyway. Of course now neither p or q can be 1 when only one of them needs to be bigger than 1, but I'm not sure.

 

[Office_Shredder]

That's the idea. Let's just consider the first inductive step. We know it's true when max(p,q)=1. If max(p,q)=2, then we could have p=2 and q=1. p-1=1 but q-1=0, so the inductive hypothesis doesn't hold (I'm assuming your natural numbers start at 1 because that was your first step)

 

[Dick]

You might want to explain more clearly why it's true if n=1. Then you will see Office_Shedder's point better about why it doesn't induct to n=2.

 

[mmmboh]

It's true if n=1 because if p and q are both natural numbers and their maximum is 1, well the first natural number is 1, so p and q must both be 1, otherwise one would be less than 1 but then it's not a natural number.

 

[Dick]

It's true if n=1 because if p and q are both natural numbers and their maximum is 1, well the first natural number is 1, so p and q must both be 1, otherwise one would be less than 1 but then it's not a natural number.

Fine, so what step in the induction fails at n=2?

 

[mmmboh]

If p is 1, then p-1=0, but the induction hypothesis was for p and q natural, so we are eliminating the possibility that p or q is 1 (so must be at least 2), which would mean the base number we chose doesn't work here...

 

[Dick]

If p is 1, then p-1=0, but the induction hypothesis was for p and q natural, so we are eliminating the possibility that p or q is 1 (so must be at least 2), which would mean the base number we chose doesn't work here...

Absolutely correct. As Office_Shredder said.

 

[mmmboh]

Ok thanks guys!