Results 1 to 9 of 9

Math Help - Can you help me prove or disprove this floor/ceiling equation?

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    19

    Can you help me prove or disprove this floor/ceiling equation?

    Can you prove or disprove this floor/ceiling equation for positive integers k and b, b \geq 2?
    \lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{\left( k+1 \right)} \rceil

    I think I can prove the equation when either k or k+1 is a positive integer power of b as follows.

    When k=b^n for positive integer n, the original equation becomes \lceil \log_{b}{\left( b^n + 1 \right)} \rceil = n + 1. Which can be proven because 0 < \log_{b}{\left( b^n + 1 \right)} - n < 1.

    Similarly, when k+1=b^n for positive integer n, the original equation becomes \lfloor \log_{b}{\left( b^n-1 \right)}\rfloor = n-1. Like before, this is easy to prove because 0 < n - \log_{b}{\left( b^n-1 \right)} \leq 1.

    Is this correct so far? I'm not sure what implications this has for when neither k nor k+1 is a positive integer power of b. Any pointers you can offer will be greatly appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,113
    Thanks
    325
    You're saying that  log_b (b^n+1) = n + 1? . That is not correct. To see that it is incorrect, try setting b=10 and n = 2:

    <br />
log_{10}101 = 2.004 \ne 2+1<br />

    I would approach it like this - given:

    <br />
(log_b k) + 1 = log_b(k+1)<br />

    raise both sides to the b power:
    <br />
b^{(log_b k) + 1} = b^{log_b(k+1)} <br />
    <br />
b^{(log_b k)} b^1 = k+1 <br />
    <br />
kb = k+1<br />
    <br />
k = \frac 1 {b-1}<br />

    Clearly if b is greater than or equal to 2 then k can not be an integer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    If \lfloor\log_bk\rfloor = n then n\leqslant \log_bk < n+1, and so b^n \leqslant k < b^{n+1}. But k and b^{n+1} are both integers, and it follows that b^n < k+1 \leqslant b^{n+1}. Hence n < \log_b(k+1) \leqslant n+1, which is equivalent to \lceil\log_b(k+1)\rceil = n+1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,113
    Thanks
    325
    Quote Originally Posted by Opalg View Post
    Hence n < \log_b(k+1) \leqslant n+1,
    So far so good...

    Quote Originally Posted by Opalg View Post
    which is equivalent to \lceil\log_b(k+1)\rceil = n+1.
    I don't agree. This would be true IF \lceil\log_b(k+1)\rceil is an integer, but that hasn't been stated. Again, using the example of b=10, k=100, and n = 2, it is true that 2 < \log_{10}(100+1) \leqslant 2+1, but not that \lceil\log_{10}(100+1)\rceil = 2+1
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ebaines View Post
    This would be true IF \lceil\log_b(k+1)\rceil is an integer, but that hasn't been stated.
    The definition of the ceiling function \lceil x\rceil is that it is the smallest integer greater than or equal to x. In particular, it is always an integer.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,113
    Thanks
    325
    Quote Originally Posted by Opalg View Post
    The definition of the ceiling function \lceil x\rceil is that it is the smallest integer greater than or equal to x. In particular, it is always an integer.
    Ahh! Thanks for that. I missed the "funny brackets" meaning floor and celing functions.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2009
    Posts
    19
    \lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{\left( k+1 \right)} \rceil

    You'll probably recognize \lfloor \log_{b}{k} \rfloor + 1 as the usual way of finding the number of digits used to represent positive integer k in base b positional notation.

    So now I'm trying to prove the equation by proving that the number of digits of k in base b can be identified as \lceil \log_{b}{\left( k+1 \right)} \rceil. I think I've got it but I'll post my results shortly for you kind folks to critique.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Aug 2009
    Posts
    19

    Verify?

    Quote Originally Posted by Andre View Post
    Can you prove or disprove this floor/ceiling equation for positive integers k and b, b \geq 2?
    \lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{\left( k+1 \right)} \rceil
    Let positive integer m be the number of digits used to represent positive integer k in base b notation.

    We know immediately that b^{m-1} is the smallest integer that uses m digits in base b, so b^{m-1} \leq k \Longrightarrow m \leq \log_{b}{k}+1.

    We also know that b^m - 1 is the largest integer that uses m digits in base b, so b^m - 1 \geq k \Longrightarrow m \geq \log_{b}{\left( k+1 \right)}.

    b^m>k \Longrightarrow m > \log_{b}{k}

    \log_{b}{k} < m \leq \log_{b}{k}+1 \Longleftrightarrow m = \lfloor \log_{b}{k} \rfloor + 1

    It could also be stated that \log_{b}{\left( k+1 \right)} \leq m \leq \log_{b}{k}+1.

    \log_{b}{\left( k+1 \right)}+1 > \log_{b}{k}+1

    \log_{b}{\left( k+1 \right)} \leq m < \log_{b}{\left( k+1 \right)}+1 \Longleftrightarrow m = \lceil \log_{b}{\left( k+1 \right)} \rceil


    First of all, is this correct? Second, how would you word this more formally and/or elegantly? I'm working on a CS paper where math is not the focus, but of course it must be correct, and it might as well be pretty. Thanks!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Aug 2009
    Posts
    19
    Looking back, that last attempt was misleading at best. I don't know why this one has been so hard for me to figure out. This should be better:

    \lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{\left( k+1 \right)} \rceil

    Let positive integer m be the number of digits used to represent positive integer k in base b notation.
    1. We know immediately that b^{m-1} is the smallest integer that uses m digits in base b, so b^{m-1} \leq k \Longrightarrow m \leq \log_{b}{k}+1.

    2. We also know that b^m - 1 is the largest integer that uses m digits in base b, so b^m - 1 \geq k \Longrightarrow m \geq \log_{b}{\left( k+1 \right)}.

    3. We could say that \log_{b}{k} < \log_{b}{\left( k+1 \right)} \leq m \leq \log_{b}{k}+1.

    4. There exists exactly one integer m which satisfies \log_{b}{k} < m \leq \log_{b}{k}+1.

    5. Since every integer power of b is itself an integer, there does not exist an integer m to satisfy \log_{b}{k} < m < \log_{b}{\left( k+1 \right)}.

    6. Therefore, there exists exactly one integer m which satisfies \log_{b}{\left( k+1 \right)} \leq m \leq \log_{b}{k}+1.

    7. Equivalently, \lceil \log_{b}{\left( k+1 \right)} \rceil = m = \lfloor \log_{b}{k} \rfloor + 1.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Ceiling and Floor
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: November 14th 2010, 05:47 PM
  2. ceiling and floor functions
    Posted in the LaTeX Help Forum
    Replies: 1
    Last Post: October 21st 2010, 04:24 PM
  3. Floor and Ceiling stuff.
    Posted in the Calculus Forum
    Replies: 5
    Last Post: October 20th 2009, 03:42 PM
  4. Help with floor and ceiling functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 9th 2009, 10:30 PM
  5. Simplification Of Floor and Ceiling functions..
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum