1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by Induction

  1. Feb 14, 2008 #1

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    1. The problem statement, all variables and given/known data

    Explain what is wrong with the structure and/or reasoning of the following proof. Remember that saying the claim is false is not a justification.

    For all x,y,n in {0,1,2,...}, if max(x,y) = n, then x=y.

    Proof (by induction):

    Base case: Suppose that n=0. If max(x,y) = 0 and x,y are in {0,1,2,...}, then x = y = 0.

    Induction step: Assume that whenever we have max(x,y) = k, then x = y must follow. Next, suppose x,y are such that max(x,y) = k+1. Then it follows that max(x-1,y-1) = k, so by the inductive hypothesis, x-1 = y-1 ==> x = y, completing the induction step.


    2. Relevant equations

    N/A

    3. The attempt at a solution

    The claims is obviously false, but I cannot say for sure exactly where the reasoning fails. I think it has something to do with the statement: "Then it follows that max(x-1,y-1) = k."

    Somehow, this must not be valid. I just don't know why. Can anyone shed light on this.
     
  2. jcsd
  3. Feb 14, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If x and y are in N={0,1,2,..} it isn't necessarily true that x-1 and y-1 are in N. If you want to show max(0,1)=1 implies 0=1, you are looking at max(-1,0)=0. That isn't covered in the k=0 case.
     
  4. Feb 15, 2008 #3

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't know how to mark a thread as solved, but thanks for the help. That makes sense
     
  5. Feb 15, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    It is possible that either x or y is equal to 0. If x= 0, then x-1 is not in the set 0, 1, 2, .... Same if y= 0.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by Induction
  1. Induction Proofs (Replies: 3)

  2. Induction Proof (Replies: 11)

  3. Induction proof (Replies: 4)

  4. Proof by induction (Replies: 12)

  5. Proof by induction (Replies: 7)

Loading...