Results 1 to 5 of 5

Math Help - What's wrong with this proof (complete induction)

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    3

    What's wrong with this proof (complete induction)

    I've been having a bit of a a think about this question but still haven't come up with a particuarly good answer yet.

    So what's wrong with the following proof that x^n=1 for all non negative intergers n, and all non zero real x. Let P(n) be the proposition that x^n=1.

    The base case x^0=1 (so that's fine)

    Inductive hypothesis: suppose n greater than equal to 0, and that P(m) true for all m less than or equal to n. (i.e we're assuming everything up to P(n) is true. Then x^n=x^(n-1)=1 based on our assumption.

    Then x^(n+1)=(x^n*x^n)/(x^(n-1))=1*1/1=1

    So p(n+1) is true. So by complete induction P(n) is true.

    Thanks in advance
    *
    Last edited by Power Out; April 4th 2009 at 07:38 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Power Out View Post
    I've been having a bit of a a think about this question but still haven't come up with a particuarly good answer yet.

    So what's wrong with the following proof that x^n=1 for all non zero intergers n, and all non zero real x. Let P(n) be the proposition that x^n=1.

    The base case x^0=1 (so that's fine)

    Inductive hypothesis: suppose n greater than equal to 0, and that P(m) true for all m less than or equal to n. (i.e we're assuming everything up to P(n) is true. Then x^n=x^(n-1)=1 based on our assumption.

    Then x^(n+1)=(x^n*x^n)/(x^(n-1))=1*1/1=1

    So p(n+1) is true. So by complete induction P(n) is true.

    Thanks in advance
    *
    the error occurs at the base case. the claim was for nonzero (positive) n. so using the base case n = 0 was invalid. the base case would be that x^1 = 1. but then that would mean x = 1. and in that case, x^n = 1. thus the claim is false since it says x can be any nonzero real number, the faulty base case got you around this though
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    3
    Sorry my fault I did mean to put for all non negative intergers n, rather than all non zero, x can be any non zero real (I've edited the original post now).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2009
    Posts
    3
    Just been looking at the proof a bit more, think I may have got somewhere.

    We've assumed that P(m) is true for all m less than or equal to n, and n is greater than or equal to 0.

    From this we got x^n=x^(n-1)=1.

    If we choose n=0 then we're told to assume x^n=1. But n-1=-1, which isn't greater than or equal to 0. As such we can't assume that x^n-1=1.

    Hence x^(n+1)= (x^n*x^n)/x^(n-1)=1.1/1=1 only when n is greater than or equal to 1. So the problem is getting between the base case and the n=1 step (one doesn't lead to the other).

    This seems right as if you know x^1=1 it follows that x^2=x*x=1, x^3=x*x*x=1 and so on. But just knowing x^0=1 doesn't enable you to say x^1=1.

    Does this sound along the right lines?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Induction

    Hello Power Out
    Quote Originally Posted by Power Out View Post
    Just been looking at the proof a bit more, think I may have got somewhere.

    We've assumed that P(m) is true for all m less than or equal to n, and n is greater than or equal to 0.

    From this we got x^n=x^(n-1)=1.

    If we choose n=0 then we're told to assume x^n=1. But n-1=-1, which isn't greater than or equal to 0. As such we can't assume that x^n-1=1.

    Hence x^(n+1)= (x^n*x^n)/x^(n-1)=1.1/1=1 only when n is greater than or equal to 1. So the problem is getting between the base case and the n=1 step (one doesn't lead to the other).

    This seems right as if you know x^1=1 it follows that x^2=x*x=1, x^3=x*x*x=1 and so on. But just knowing x^0=1 doesn't enable you to say x^1=1.

    Does this sound along the right lines?
    Yes. The fact is that, no matter where you start, you'll always need two consecutive integers n and (n-1) for which x^n =1 and x^{n-1} = 1, in order to be able to construct the expression \frac{x^nx^n}{x^{n-1}}. And you simply don't have that for any base case.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 10th 2011, 02:13 PM
  2. Replies: 3
    Last Post: October 12th 2010, 09:11 PM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Complete Induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 22nd 2009, 07:41 AM
  5. proof by complete induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 25th 2007, 02:09 PM

Search Tags


/mathhelpforum @mathhelpforum