Proof by Induction

1. Feb 14, 2008

cepheid

Staff Emeritus
1. The problem statement, all variables and given/known data

Explain what is wrong with the structure and/or reasoning of the following proof. Remember that saying the claim is false is not a justification.

For all x,y,n in {0,1,2,...}, if max(x,y) = n, then x=y.

Proof (by induction):

Base case: Suppose that n=0. If max(x,y) = 0 and x,y are in {0,1,2,...}, then x = y = 0.

Induction step: Assume that whenever we have max(x,y) = k, then x = y must follow. Next, suppose x,y are such that max(x,y) = k+1. Then it follows that max(x-1,y-1) = k, so by the inductive hypothesis, x-1 = y-1 ==> x = y, completing the induction step.

2. Relevant equations

N/A

3. The attempt at a solution

The claims is obviously false, but I cannot say for sure exactly where the reasoning fails. I think it has something to do with the statement: "Then it follows that max(x-1,y-1) = k."

Somehow, this must not be valid. I just don't know why. Can anyone shed light on this.

2. Feb 14, 2008

Dick

If x and y are in N={0,1,2,..} it isn't necessarily true that x-1 and y-1 are in N. If you want to show max(0,1)=1 implies 0=1, you are looking at max(-1,0)=0. That isn't covered in the k=0 case.

3. Feb 15, 2008

cepheid

Staff Emeritus
I don't know how to mark a thread as solved, but thanks for the help. That makes sense

4. Feb 15, 2008

HallsofIvy

Staff Emeritus
It is possible that either x or y is equal to 0. If x= 0, then x-1 is not in the set 0, 1, 2, .... Same if y= 0.