Results 1 to 9 of 9

Thread: 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 $\displaystyle k$ and $\displaystyle b$, $\displaystyle b \geq 2$?
    $\displaystyle \lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{\left( k+1 \right)} \rceil$

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

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

    Similarly, when $\displaystyle k+1=b^n$ for positive integer $\displaystyle n$, the original equation becomes $\displaystyle \lfloor \log_{b}{\left( b^n-1 \right)}\rfloor = n-1$. Like before, this is easy to prove because $\displaystyle 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 $\displaystyle k$ nor $\displaystyle k+1$ is a positive integer power of $\displaystyle 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,389
    Thanks
    420
    You're saying that $\displaystyle log_b (b^n+1) = n + 1? $. That is not correct. To see that it is incorrect, try setting b=10 and n = 2:

    $\displaystyle
    log_{10}101 = 2.004 \ne 2+1
    $

    I would approach it like this - given:

    $\displaystyle
    (log_b k) + 1 = log_b(k+1)
    $

    raise both sides to the b power:
    $\displaystyle
    b^{(log_b k) + 1} = b^{log_b(k+1)}
    $
    $\displaystyle
    b^{(log_b k)} b^1 = k+1
    $
    $\displaystyle
    kb = k+1
    $
    $\displaystyle
    k = \frac 1 {b-1}
    $

    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
    10
    If $\displaystyle \lfloor\log_bk\rfloor = n$ then $\displaystyle n\leqslant \log_bk < n+1$, and so $\displaystyle b^n \leqslant k < b^{n+1}$. But k and $\displaystyle b^{n+1}$ are both integers, and it follows that $\displaystyle b^n < k+1 \leqslant b^{n+1}$. Hence $\displaystyle n < \log_b(k+1) \leqslant n+1$, which is equivalent to $\displaystyle \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,389
    Thanks
    420
    Quote Originally Posted by Opalg View Post
    Hence $\displaystyle n < \log_b(k+1) \leqslant n+1$,
    So far so good...

    Quote Originally Posted by Opalg View Post
    which is equivalent to $\displaystyle \lceil\log_b(k+1)\rceil = n+1$.
    I don't agree. This would be true IF $\displaystyle \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 $\displaystyle 2 < \log_{10}(100+1) \leqslant 2+1$, but not that $\displaystyle \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
    10
    Quote Originally Posted by ebaines View Post
    This would be true IF $\displaystyle \lceil\log_b(k+1)\rceil $ is an integer, but that hasn't been stated.
    The definition of the ceiling function $\displaystyle \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,389
    Thanks
    420
    Quote Originally Posted by Opalg View Post
    The definition of the ceiling function $\displaystyle \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
    $\displaystyle \lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{\left( k+1 \right)} \rceil$

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

    So now I'm trying to prove the equation by proving that the number of digits of $\displaystyle k$ in base $\displaystyle b$ can be identified as $\displaystyle \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 $\displaystyle k$ and $\displaystyle b$, $\displaystyle b \geq 2$?
    $\displaystyle \lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{\left( k+1 \right)} \rceil$
    Let positive integer $\displaystyle m$ be the number of digits used to represent positive integer $\displaystyle k$ in base $\displaystyle b$ notation.

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

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

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

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

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

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

    $\displaystyle \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:

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

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

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

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

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

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

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

    7. Equivalently, $\displaystyle \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: Nov 14th 2010, 05:47 PM
  2. ceiling and floor functions
    Posted in the LaTeX Help Forum
    Replies: 1
    Last Post: Oct 21st 2010, 04:24 PM
  3. Floor and Ceiling stuff.
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Oct 20th 2009, 03:42 PM
  4. Help with floor and ceiling functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Aug 9th 2009, 10:30 PM
  5. Simplification Of Floor and Ceiling functions..
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Apr 29th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum