Results 1 to 12 of 12
Like Tree1Thanks
  • 1 Post By skeeter

Thread: Does this proof contain an error

  1. #1
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Does this proof contain an error

    Does this proof contain an error-screen-shot-2017-01-05-9.14.22-am.png
    Does this proof contain an error-screen-shot-2017-01-05-9.21.09-am.png

    You will notice in the final step that 11.4.2 was used as a justification for  \log_2 n = k
    however, from the first line we recall that  2^k < n < 2^{k+1} which means that we should not be able to
    use 11.4.2 as a justification.

    Is my book wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,732
    Thanks
    2456
    Awards
    1

    Re: Does this proof contain an error

    Quote Originally Posted by mdm508 View Post
    Click image for larger version. 

Name:	Screen Shot 2017-01-05 at 9.14.22 AM.png 
Views:	15 
Size:	115.6 KB 
ID:	36839
    Click image for larger version. 

Name:	Screen Shot 2017-01-05 at 9.21.09 AM.png 
Views:	25 
Size:	21.8 KB 
ID:	36840

    You will notice in the final step that 11.4.2 was used as a justification for  \log_2 n = k
    however, from the first line we recall that  2^k < n < 2^{k+1} which means that we should not be able to
    use 11.4.2 as a justification.

    Is my book wrong?
    What is 11.4.2?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2014
    From
    Illinois
    Posts
    233
    Thanks
    85

    Re: Does this proof contain an error

    Quote Originally Posted by mdm508 View Post
    You will notice in the final step that 11.4.2 was used as a justification for  \log_2 n = k
    however, from the first line we recall that  2^k < n < 2^{k+1} which means that we should not be able to
    use 11.4.2 as a justification.
    Why not? It appears to be a simple application of 11.4.2, what's wrong with that?

    Quote Originally Posted by Plato View Post
    What is 11.4.2?
    There are two image attachments - open the first then click on "Next" and you'll see the second image.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    15,520
    Thanks
    3388

    Re: Does this proof contain an error

    Quote Originally Posted by Plato View Post
    What is 11.4.2?
    Thanks from mdm508
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,732
    Thanks
    2456
    Awards
    1

    Re: Does this proof contain an error

    Quote Originally Posted by ChipB View Post
    Why not? It appears to be a simple application of 11.4.2, what's wrong with that?
    There are two image attachments - open the first then click on "Next" and you'll see the second image.
    Thank you and Skeeter both. Yet for some reason that usual trick still does work for me.
    I do see the objection. The inequality is less-than or equal in 11.4.2 but in the one on which it is used.
    However, it is true that if $2^k<x<2^{k+1}$ then $k<\log_2(x)<k+1$; the log function is monotone.
    The because the is no integer between integers $k~\&~k+1$ we get $\left\lfloor\log_2(x)\right\rfloor=k$.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: Does this proof contain an error

    Quote Originally Posted by Plato View Post
    the log function is monotone.
    I am not familiar with this concept. Would you mind fleshing this out for me? I looked on wikipedia and they define monotone with more concepts I don't know.
    Usually to be able to apply the floor function and get k, we need something of the form
     k \le x < k + 1~ \text{if the former is the case we know that} floor(x) = k .
    Clearly that is not the case here. I understand your saying there is something special about the log function that allows us to obtain k. Could you explain what that something is.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,732
    Thanks
    2456
    Awards
    1

    Re: Does this proof contain an error

    Quote Originally Posted by mdm508 View Post
    I am not familiar with this concept. Would you mind fleshing this out for me? I looked on wikipedia and they define monotone with more concepts I don't know.
    Monotone, simply means to preserve order. Non-increasing or non-decreasing function.

    Quote Originally Posted by mdm508 View Post
    Usually to be able to apply the floor function and get k, we need something of the form
     k \le x < k + 1~ \text{if the former is the case we know that} floor(x) = k . Clearly that is not the case here. I understand your saying there is something special about the log function that allows us to obtain k. Could you explain what that something is.
    This really is not special to the log function. It has everything to do with the floor function. We prove that for any real number $t$ there is a unique integer $\left\lfloor t \right\rfloor$ that has the property that $\Large{\left\lfloor t \right\rfloor\le t<\left\lfloor t \right\rfloor+1}$.

    There are nine integers from $2^3=8$ to $2^4=16$
     \begin{align*}\text{If  }{2^k}& < t < {2^{k + 1}}\\{\log _2}({2^k}) &< {\log _2}(t) < {\log _2}({2^{k + 1}})\\k &\le \left\lfloor {{{\log }_2}(t)} \right\rfloor  < k + 1\\k &= \left\lfloor {{{\log }_2}(t)} \right\rfloor \end{align*}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: Does this proof contain an error

    Quote Originally Posted by Plato View Post
     \begin{align*}{\log _2}({2^k}) &< {\log _2}(t) < {\log _2}({2^{k + 1}})\\k &\le \left\lfloor {{{\log }_2}(t)} \right\rfloor  < k + 1\end{align*}
    how are we allowed to switch from  <~\text{to }\le
    Last edited by mdm508; Jan 5th 2017 at 03:10 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,732
    Thanks
    2456
    Awards
    1

    Re: Does this proof contain an error

    Quote Originally Posted by mdm508 View Post
    how are we allowed to switch from  <~\text{to }\le
    Face it, you are just not ready to do this level of proof.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: Does this proof contain an error

    Quote Originally Posted by Plato View Post
    Face it, you are just not ready to do this level of proof.
    Your right! I need to really go back and learn all my algebra all over again. I'm just worried cause i have an algorithms course coming which is very proof heavy. And it worries me i can't do a one as basic as this
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: Does this proof contain an error

    Quote Originally Posted by Plato View Post
    The because the is no integer between integers k~\&~k+1$ we get $\left\lfloor\log_2(x)\right\rfloor=k.
    However, i think this is the answer to why we are able to switch from < to <=.
    Last edited by mdm508; Jan 5th 2017 at 09:12 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: Does this proof contain an error

    thought about it some more, you can switch from < to <= because of a simple mathematical fact,
    if something is < then its surely less than or equal. 2 < 6 and its also true that 2 <= 6. So we can apply the theorem with no problems.

    Why didn't you just say this? I realized I want to react more strongly to this. You have no business assessing my mathematical capabilities. Furthermore, it is not helpful to me developing my skills. It only served to make me feel discouraged.
    Last edited by mdm508; Jan 9th 2017 at 10:51 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Odd proof - Can you spot the error?
    Posted in the Math Puzzles Forum
    Replies: 14
    Last Post: Mar 8th 2010, 03:57 PM
  2. Mean square error proof
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Feb 23rd 2009, 05:51 PM
  3. Finding an error in a proof (topology)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 1st 2009, 12:50 AM
  4. Error-correcting code proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 18th 2008, 10:21 PM
  5. Error in Complex Analysis Proof
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 25th 2007, 08:24 AM

/mathhelpforum @mathhelpforum