Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By JeffM

Math Help - What's wrong with the following proof? (Strong induction)

  1. #1
    Junior Member
    Joined
    Oct 2012
    From
    London
    Posts
    54

    What's wrong with the following proof? (Strong induction)

    Statement: For any integer  n\geq 0, (x^n)'=0

    Proof

    Base Case: For  n=0, x^0=1, so \, (x^0)'=(1)'=0

    Induction hypothesis: Assume that for some  k, (x^i)'=0 for all  0 \leq i \leq k

    Induction step: Consider  x^{k+1} . Note that  x^{k+1} = x* x^k

    Using product rule,  (x^{k+1})'=(x*x^k)'=x*(x^k)' + (x)'*x^k

    By induction hypothesis, ( x^k)'=0 and (x)'=0 . Therefore,  (x^{k+1})'=0. So the result holds by induction



    I know this statement is obviously false, but I can't seem to find anything wrong with the proof that is provided.
    I looked through my notes and it looks like every step of the induction process is followed correctly.
    Can someone please help me figure out which part is wrong? or give me a hint?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    768
    Thanks
    390

    Re: What's wrong with the following proof? (Strong induction)

    $x' = 1 \ne 0.$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    768
    Thanks
    390

    Re: What's wrong with the following proof? (Strong induction)

    Upon reflection, my post above is too curt.

    When you show that $(x^0)' = 0$ you have proved that

    $the\ set\ J\ such\ that\ i \in J \implies i \in \mathbb Z\ and\ i \ge 0\ and\ (x^i)' = 0\ is\ not\ empty.$

    Thus I dislike the traditional phraseology "$Assume\ for\ some\ integer\ k \ge 0\ that\ (x^k)' = 0."$

    You have proved that J contains at least one such integer. So I prefer to say, "Let k be any member of J." But you have not proved that 1 is in set J, and so (x1)' = 0 is not permissible (as well as being false).
    Last edited by JeffM; May 24th 2014 at 08:21 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    688
    Thanks
    281

    Re: What's wrong with the following proof? (Strong induction)

    Hi,
    I hope this helps. Whenever doing a "strong" inductive proof, it's probably a bad idea to use n+1 as m as in the following:

    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: What's wrong with the following proof? (Strong induction)

    Hint: what happens for k = 1?

    A variation of this proof is used to prove that all horses are the same color. Basically, you are using the wrong base case.
    Last edited by Deveno; May 24th 2014 at 11:12 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,238
    Thanks
    1795

    Re: What's wrong with the following proof? (Strong induction)

    Quote Originally Posted by nubshat View Post
    Statement: For any integer  n\geq 0, (x^n)'=0

    Proof

    Base Case: For  n=0, x^0=1, so \, (x^0)'=(1)'=0

    Induction hypothesis: Assume that for some  k, (x^i)'=0 for all  0 \leq i \leq k

    Induction step: Consider  x^{k+1} . Note that  x^{k+1} = x* x^k

    Using product rule,  (x^{k+1})'=(x*x^k)'=x*(x^k)' + (x)'*x^k

    By induction hypothesis, ( x^k)'=0 and (x)'=0 .
    This step does not work for k= 0 because you are using " (x)'= 0 before you have proved it.

    Therefore,  (x^{k+1})'=0. So the result holds by induction



    I know this statement is obviously false, but I can't seem to find anything wrong with the proof that is provided.
    I looked through my notes and it looks like every step of the induction process is followed correctly.
    Can someone please help me figure out which part is wrong? or give me a hint?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by strong induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 27th 2011, 05:06 PM
  2. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 27th 2009, 07:30 AM
  3. Proof Using Strong Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 23rd 2009, 11:26 AM
  4. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 01:42 PM
  5. Strong induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2008, 10:48 PM

Search Tags


/mathhelpforum @mathhelpforum