Proving theroms? Ugh!

[Zej]

I've been stumped on this stupid question for 3 days, guys. I have to locate the flaw in this proof. I have no clue what's wrong with it. According to the rules of inductive reasoning, it works

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

[TheManWhoCan]

How's about a counterexample:

max(3,17) = 17

but 3 does not equal 17...

[opus]

"Suppose that n=1. If max(x,y) = 1 and x and y are positive integers, we have x=1 and y=1. "
That is only true for n=1, because only "1" is less or equal to n. So x must equal y. Buf if there are more possible integers, that's not true.

[Kalkewl8ter]

The induction fails when you go from k=1 to k=2. If you have max(2, 1)=2 for your equation max(x, y)=k+1, then you cannot take max(x-1, y-1) as part of the domain of the "theorem" since y-1=0, which is not a positive integer. Therefore, the only case you are allowed to consider in your "proof" for max(x, y)=k+1 when k=1 is max(2, 2)=2, in which case x=y is certainly true. This proof leaves out the simplest counter-example, and thus, by the nature of induction, all of the other counter-examples.

[sql_lall]

It's all about forgetting the negatives / zero...

u see, if max(x,y) = 1, then x doesn't have to = y, it could be x = 0, y = 1, or x = 1, y = -1244129!

This plays a big part, because the inductive step says that if max(x,y) = k+1, then max(x-1, y-1) = k

looking at k = 2: max(2, 1) = 2 => max(1, 0) = 1!!!
U see, we now have max(x,y) = 1 without x = y


I have no idea where this max(x,y) = 1 -> x = y = 1 came from!

[Kalkewl8ter]

sql_lall,
It says x and y are positive integers.

[sql_lall]

So? it doesn't say x-1 and y-1 are....
so the assumption max(x-1, y-1) = 1 => x = y = 2 is false...

cos as we all know, x - 1 = 0 is a possible solution

[fundu]

I think we cannot use Induction here as your hypothesis is already wrong. This point is already proved by many people.

Moreover a counter example is enough to disprove any theorem as that is being already given.

[ZaidGS]

well, FOR SURE, the assumption that
max(x,y)=k ==>x=y
is WRONG.
but i can see something right that Zej saying,
but he made a big error then.
if
max(x,y)=k then
x=k OR y=k
note thats its OR not AND
thats the mistake you fell for.

example
max(10,-20)=10
so if we have:
max(x,y)=10
we know that AS LEAST ONE of x, and y is 10,
BUT not nessarilly both.

hope this helps you Zej