Results 1 to 2 of 2

Math Help - Interesting question on mathematical induction

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    Interesting question on mathematical induction

    I read this recently. I will try to define the terms carefully.
    N - Set of Naturals
    max(a,b) is defined in the standard way

    Consider the following argument based on the Principle of Mathematical Induction.

    P(n): For all a,b in N, if max(a,b)=n => a=b=n
    Proof:
    1. P(1) is obviously true. As, for all a,b in N, if max(a,b)=1 => a=b=1.
    2. Assume P(r) is true. i.e. For all a,b in N, if max(a,b)=r => a=b=r
    3. Now let there be some a,b in N such that max(a,b)=r+1. Consider a-1,b-1. Now max(a-1,b-1)=r. So under the assumption that P(r) is true, we have a-1=b-1 => a=b. Hence we have established truth of P(r+1).
    And, thus by the Principle of Mathematical Induction, P(n) is true for all n in N.

    So where is the goof-up? Here is my counter-argument.
    If I am to pin-point the logical error in the above proof it has to be - I have not demonstrated P(r+1) is true for all a,b in N. I have only shown it to be true under the case where a>1 and b>1. (Because it is only then a-1 and b-1 can be defined). So for the case where one of then, say a, is equal to 1, I can't use P(r) as a-1 is not defined in N. And P(r+1) is obviously false when a=1. Hence the proof is flawed.

    Can someone please help me in critically reviewing my counter-argument to the proposed proof? I am looking for a very specific logical flaw in the proposed proof. (And, I think I have captured it 'completely' in my counter argument).
    PS: My argument becomes more evident when we look at what happens to P(2) given P(1) is true for all a,b.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Mathematical induction - Wikipedia, the free encyclopedia - specifically the part about Pólya's proof.

    This is virtually the same as Pólya's induction that all horses are of the same color -- P(2) is not true. max(1,2) = 2, yet 1 \neq 2. The induction step does not work here because 1-1=0 \notin \mathbb{N}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 4th 2011, 06:30 PM
  2. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 29th 2010, 11:31 AM
  3. Mathematical Induction question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 26th 2009, 08:05 PM
  4. Need help on Mathematical Induction question
    Posted in the Algebra Forum
    Replies: 5
    Last Post: October 27th 2008, 10:32 AM
  5. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 23rd 2008, 10:40 PM

Search Tags


/mathhelpforum @mathhelpforum