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

1. ## 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!

2. 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:

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

I would approach it like this - given:

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

raise both sides to the b power:
$
b^{(log_b k) + 1} = b^{log_b(k+1)}
$

$
b^{(log_b k)} b^1 = k+1
$

$
kb = k+1
$

$
k = \frac 1 {b-1}
$

Clearly if b is greater than or equal to 2 then k can not be an integer.

3. 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$.

4. Originally Posted by Opalg
Hence $n < \log_b(k+1) \leqslant n+1$,
So far so good...

Originally Posted by Opalg
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$

5. Originally Posted by ebaines
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.

6. Originally Posted by Opalg
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.

7. $\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.

8. ## Verify?

Originally Posted by Andre
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!

9. 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$.