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 !

• Why was the question downvoted :(? What is wrong with it? – Ar Co Jan 29 '15 at 10:08
• It was downvoted before the edit, I think. – TonyK Jan 29 '15 at 10:08
• You can't allow $i = M$. – TonyK Jan 29 '15 at 10:09
• @TonyK - good point, thanks! I've replaced $M-i$ by $x$, it is also more understandable now. – Ar Co Jan 29 '15 at 10:16

We use the following lemma: $\lceil x+y \rceil \le \lceil x\rceil + \lceil y\rceil.$
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*}