# Can't find the mistake in my inductive step

Few days ago I was solving some induction execises, and I tried and solved this one.

# Statement

What is wrong with this “proof”?

“Theorem” For every positive integer $$n$$, if $$x$$ and $$y$$ are positive integers with $$\max(x, y) = n$$, then $$x = y$$.

Basis Step: Suppose that $$n = 1$$. If $$\max(x, y) = 1$$ and $$x$$ and $$y$$ are positive integers, we have $$x = 1$$ and $$y = 1$$.

Inductive Step: Let $$k$$ be a positive integer. Assume that whenever $$\max(x, y) = k$$ and $$x$$ and $$y$$ are positive integers, then $$x = y$$. Now let $$\max(x, y) = k + 1$$, where $$x$$ and $$y$$ are positive integers. Then $$\max(x − 1, y − 1) = k$$, so by the inductive hypothesis, $$x − 1 = y − 1$$. It follows that $$x = y$$, completing the inductive step.

# Solution, taken from the original book

The mistake is in applying the inductive hypothesis to look at $$\max(x − 1, y − 1)$$, because even though $$x$$ and $$y$$ are positive integers, $$x − 1$$ and $$y − 1$$ need not be (one or both could be 0)

# Now my question

After solving the problem I wrote my own inductive step, assuming the same hypothesis. I did it just for fun, but now, even knowing that my inductive step is wrong, I can't find the mistake. I need to know what is wrong in my inductive step and why.

# My inductive step

Inductive Step: Let $$k$$ be a positive integer. Assume that whenever $$\max(x, y) = k$$ and $$x$$ and $$y$$ are positive integers, then $$x = y$$. Since $$\max(x, y) = k$$ and $$x$$ and $$y$$ are positive integers with$$x = y$$, I add $$1$$ to both $$x$$ and $$y$$. Then $$\max(x + 1, y + 1) = k + 1$$. It follows that $$x + 1 = y + 1$$ because $$x = y$$, completing the inductive step.

• Can you find what's wrong with this? ​ ​ ​ If p then p. ​ In particular, if False then False. ​ Since False, False. ​ It follows that False is true. ​ ​ ​ ​ ​ ​ ​ ​ – user57159 Jan 17 '17 at 13:50

The statement you are claiming to prove is the statement

If $\max(x,y)=n$, then $x=y$.

However, the statement you prove is the statement

If $x=y$, then $\max(x,y)=n$

In other words, your inductive step is correct because it proves a correct statement, but not the same statement as you think you are proving.

If you really wanted to prove your statement, you would have to prove that if $\max(x+1, y+1) = k+1$, then $x+1=y+1$.

Instead, you only proved the statement if $x=y$, then $x+1=y+1$.

Another way of looking is you only indictively proved the statement for pairs $(x',y')$ which can be written as $(x+1, y+1)$, where $x,y$ are positive integers. So, you didn't prove the statement for $(0,2)$, for example.

Your inductive step is correct, but it doesn't prove the theorem, because you're working backwards:

$x=y\Rightarrow \max(x+1,y+1)=k+1.$

Whereas you should be proving:

$\max(x+1,y+1)=k+1\Rightarrow x+1=y+1$