1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user57159 Jan 17 '17 at 13:50
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.