Theorem: For every integer n, if x and y are positive integers with max(x, y) = n, then x = y.
Basic 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.
What's wrong with this proof?
max(x,y) has not been previously defined, but I assume it to be:
max(x,y)
=x if x≥y
=y if x<y.
If that is the case, then we can find numerous counter-examples to the given theorem, such as:
x=4, y=6,
n=max(x,y)=6
and x≠y !
which is sufficient proof that the theorem is false.
Notwithstanding the fallacy of the theorem, there are flaws in the proof.
Typically the inductive step is built on the case k and go on to prove that the case k+1 is true.
The assumption part is correctly made:
namely for an integer n=k, and positive integers x and y, if max(x,y)=k, then x=y. (the assumption is correctly made based on the theorem).
So for the case of n=k+1, and max(x,y)=k+1, we only know that at least one of x or y has to be k+1, not both. So there is no logical reason to conclude that both x and y equal k+1. That's where the conclusion that the proof cannot be made.
Could you check that the theorem has been transcribed correctly in the post?
Thank you for responding. Yes everything is typed correctly. I want to find what is wrong with proof.
Are you convinced that the counter example is valid? If it is, then there is no correct proof, since the theorem is not valid.
If the counter example is not valid, explain why it is not valid.
Are you sure the question is not:
"Theorem: For every integer 2n. If x and y are positive integers such that n=x+y and with max(x, y) = n, then x = y."
or did the question say:
"Prove or find a counter example"?
No, the question verbatim is "What is wrong with this proof?"
Finally, so "What is wrong with the proof" is part of the question. Sorry that I didn't understand it as such before. It seemed to me it was your proof, and I was explaining to you why you should not even try to prove a conjecture full of holes.
Assuming there was a proof, what's wrong had been stated (at 9:52 pm):
"The assumption part is correctly made:
namely for an integer n=k, and positive integers x and y, if max(x,y)=k, then x=y. (the assumption is correctly made based on the theorem).
So for the case of n=k+1, and max(x,y)=k+1, we only know that at least one of x or y has to be k+1, not both. So there is no logical reason to conclude that both x and y equal k+1. That's where the conclusion that the proof cannot be made. "
In addition, by induction, the proof should have been made for the case n+1, and not n-1.
Thank you! So, going back to your counterexample in post 9:52:
x=4, y=6,
n=max(x,y)=6
Why does it =6? Sorry if this seems like a silly question. . .
"max(x,y) has not been previously defined, but I assume it to be:
max(x,y)
=x if x≥y
=y if x<y. "
So if the above definition max(x,y) corresponds with your teacher's,
then
x=4, and y=6,
then x<y, therefore max(x,y)=y,
so max(4,6)=y.
Oh okay. . .I get it. . .Thank you so much for your help :)
Here is the solution: The mistake is in applying the inductive hypothesis to look at max(x −1, y −1) . Notice that we are doing induction on n not on x or y. Even though x and y are positive integers, x −1 and y −1 need not be (one or both could be 0). In fact, that is what happens if we let x = 1 and y = 2 when k = 1.
I have to admit I do not quite understand this explanation. . .