- #1

- 5,199

- 38

## Homework Statement

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.

## Homework Equations

N/A

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