How to prove/dispute the following log inequality? 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 !
 A: 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*}
