How to prove/dispute the following log inequality?

Question

I was wondering if the following inequality is true:

$$\forall x,N\in \mathbb N^+: \lceil \log_2\left(\lfloor\frac{N}{x}+1\rfloor\right)\rceil\leq \lceil\log_2 (N+1)\rceil - \lfloor\log_2 (x)\rfloor $$

I need this inequality to hold for my algorithm analysis: I need to store counter which could reach value $$\lfloor\frac{N}{x}\rfloor$$ using $$\lceil\log_2 (N+1)\rceil - \lfloor\log_2 (x)\rfloor$$

Bits.

(I've tried it using various values of $x,N$ and it seems to work). Thanks !

Answer 1

We use the following lemma: $\lceil x+y \rceil \le \lceil x\rceil + \lceil y\rceil.$

Proof of the log inequality:

Case 1. When $x$ divides $N$. $k=N/x$ is an integer. \begin{align*} \text{LHS}&=\left\lceil\log_2 (k+1)\right\rceil\\ &=\left\lceil\log_2 (k+1/x)\right\rceil\\ &= \left\lceil\log_2 (N+1)-\log_2 x\right\rceil\\ &\le \left\lceil\log_2 (N+1)\right\rceil+\left\lceil (-\log_2 x)\right\rceil\\ &= \left\lceil\log_2 (N+1)\right\rceil-\left\lfloor \log_2 x\right\rfloor=\text{RHS}. \end{align*}

Case 2. When $x$ doesn't divide $N$. $k=\lceil N/x\rceil$ is an integer. Since $(k-1)x<N\le kx$, $k-1+\frac1x<\frac{N+1}{x}\le k+\frac1x$. \begin{align*} \text{LHS}&=\left\lceil\log_2 k\right\rceil\\ &=\left\lceil\log_2 (k-1+1/x)\right\rceil\\ &\le \left\lceil(\log_2 \frac{N+1}{x})\right\rceil\\ &=\left\lceil\log_2 (N+1)-\log_2 x\right\rceil\\ &\le \left\lceil\log_2 (N+1)\right\rceil+\left\lceil (-\log_2 x)\right\rceil\\ &= \left\lceil\log_2 (N+1)\right\rceil-\left\lfloor \log_2 x\right\rfloor=\text{RHS}. \end{align*}