Discrete Math

posted by .

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?

  • Discrete Math -

    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?

  • Discrete Math -

    Thank you for responding. Yes everything is typed correctly. I want to find what is wrong with proof.

  • Discrete Math -

    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.

  • Discrete Math -

    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"?

  • Discrete Math -

    No, the question verbatim is "What is wrong with this proof?"

  • Discrete Math -

    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.

  • Discrete Math -

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

  • Discrete Math -

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

  • Discrete Math -

    Oh okay. . .I get it. . .Thank you so much for your help :)

  • Discrete Math -

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

  • Discrete Math -

    The inductive process is
    1. to establish for a base case, for example n=1. Then,
    2. assuming the hypothesis is true for case n (in general),
    3. we have to prove that it follows that it is true for the case n+1.

    If we are able to do all that, then the hypothesis is true for all n.

    Generally, steps 1 and 2 are easy to establish. It is in step 3 that some algebraic or logical operations are required to establish for the case of "n+1".

    In the given erroneous proof, the first two steps were correct, but the third step had something to do with x-1 and y-1, which relates to the case n-1 instead of the case n+1. Worse, neither the case n-1 nor the case n+1 had been mentioned, so step 3 had established nothing.

  • Discrete Math -

    It was proven during the previous lecture that
    1+2+3+....+n=[n(n+1)]/2.

    Using that result, find the sum of all 3-digit palindromes: a palindrome is a number that can be written as ABA, where 1=<A<=9 and 0<=B<=9. Hint: decompose ABA = 100*A + 10*B + A and use above proven result.

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. discrete math

    1)prove that if x is rational and x not equal to 0, then 1/x is rational. 2) prove that there is a positive integers that equals the sum of the positive integers not exceeding it. Is your proof constructive or nonconstructive?
  2. discrete math

    Could someone help me with this induction proof. I know its true. given then any integer m is less than or equal to 2, is it possible to find a sequence of m-1 consecutive positive integers none of which is prime?
  3. MAth

    If 1 gallon (gal) of water weighs 8.34 pounds (lb), how much does 3.75 gal weigh?
  4. behavior problems (dogs)

    please check my answer thanks You've evaluated Max, a two-year-old neutered male English Bull Terrier. You found him to be very friendly with humans; he's outgoing and confident. Max is an obedient dog and you anticipate he will do …
  5. C programming

    Question: Write a program that reads integers from the keyboard until the user enters the sentinel value -999. The program should then print the minimum integer read, the maximum integer read and the average of all the integers. (Excluding …
  6. math

    every week Brady gets $2.50 more for his allowance than Max does. They spend $6 on snacks and save the rest. Brady saves $72, but Max saves only $52. How many weeks does it take Brady to save $72?
  7. Proofs and numbers

    Prove the following theorem: Suppose p is a prime number, r, s are positive integers and x is an arbitrary integer. Then we have x^r identical to x^s (mod p) whenever r is identical to s (mod 11).for x belongs to an integer
  8. Discrete Math

    Let n be positive integer greater than 1. We call n prime if the only positive integers that (exactly) divide n are 1 and n itself. For example, the first seven primes are 2, 3, 5, 7, 11, 13 and 17. (We should learn more about primes …
  9. Math

    Paulo withdraws the same amount from his bank account each week to pay for lunch. Over the past four weeks, he withdrew one hundred twenty dollars. Which rule best applies to determine the change in his account each week?
  10. maths

    the non- decreasing sequence of odd integers {a1, a2, a3, . . .} = {1,3,3,3,5,5,5,5,5,...} each positive odd integer k appears k times. it is a fact that there are integers b, c, and d such that, for all positive integers n, añ = …

More Similar Questions