How is the inequality $\displaystyle\sum_{r=1}^k\ \Big\lceil\frac{i-1}{2^r}\Big\rceil \leq i-2+k$ acquired?

Question

Edited: The RHS should be $i-2+k$, not $i-2-k$, I made a typo. Probably needed more sleep.

---

While reading some paper about sorting algorithms, I ran through this: $$\displaystyle\sum_{r=1}^k\ \Big\lceil\frac{i-1}{2^r}\Big\rceil \leq i-2+k$$

Under the circumstances that $i=n-2^k-1$, while $2^{k}\lt n\leq 2^{k+1}-1, k\in\mathbb{N}$.

Now, I understand how geometric series are calculated, but adding the ceiling function here is totally over my capacity. By simply calculating by hand from $i=1$ and upward, I was able to get that for $i\geq2$, the result of the LHS being $\Big\lfloor\frac{i-2}{2}+k\Big\rfloor$, looking alike but not the one provided. It seems like was using the properties of ceiling functions but nothing useful comes to my mind.

It really would help if some instructions are given in the right direction or a very simple step-by-step explanation.

Thanks in advance.

Answer 1

Thanks to the comments, after a few days of struggling I finally was able to find the way to get the upper bound. To calculate the following formula, $$\displaystyle\sum_{r=1}^k\ \Big\lceil\frac{i-1}{2^r}\Big\rceil$$

What we do first is to separate it into 2 parts, the integer part and the fractal part (which would be affected by the ceiling function), getting: $$\displaystyle\sum_{r=1}^k\frac{i-1}{2^r}+\displaystyle\sum_{r=1}^k\Big(\Big\lceil\frac{i-1}{2^r}\Big\rceil-\frac{i-1}{2^r}\Big)$$

• The first term is easy to deal with. Eliminating the constant term, we get: $$(i-1)\displaystyle\sum_{r=1}^k\frac{1}{2^r}$$ which can be easily evaulated into $$(i-1)\cdot\Big(1-\frac{1}{2^k}\Big)$$

• As for the second term, we use the property that $$\begin{align} \\ \displaystyle\sum_{r=1}^k\Big(\Big\lceil\frac{i-1}{2^r}\Big\rceil-\frac{i-1}{2^r}\Big) &\leq \overbrace{\Big[\Big(1-\frac{1}{2}\Big)+\Big(1-\frac{1}{2^2}\Big)+\dots+\Big(1-\frac{1}{2^k}\Big)\Big]}^{\text{k terms}} \\ &= k-\Big[\frac{1}{2}+\frac{1}{2^2}+\dots+\frac{1}{2^k}\Big] \\ &=k-\Big[1-\frac{1}{2^k}\Big]\end{align}$$

Adding the two terms up results in $$\begin{align} \displaystyle\sum_{r=1}^k\frac{i-1}{2^r}+\displaystyle\sum_{r=1}^k\Big(\Big\lceil\frac{i-1}{2^r}\Big\rceil-\frac{i-1}{2^r}\Big)&\leq (i-1)\cdot\Big(1-\frac{1}{2^k}\Big)+k-\Big[1-\frac{1}{2^k}\Big] \\ &= i-1-\frac{i-1}{2^k}+k-1+\frac{1}{2^k} \\ &= i+k-2+\frac{2-i}{2^k} \\ \end{align}$$

Since $i\geq 2$, we are able to elimate the last term, thus obtaining the inequality stated in the question: $$\Big\lceil\frac{i-1}{2^r}\Big\rceil \leq i-2+k$$

Answer 2

if you substitute in: $$\frac{i-1}{2^r}=\frac{n-2^k-2}{2^r}$$ then you can say: $$-\frac{1}{2^{r-1}}=\frac{2^k-2^k-2}{2^r}\le\frac{n-2^k-2}{2^r}\le\frac{2^{k+1}-2^k-3}{2^r}=\frac{2^k-3}{2^r}$$ the ceiling of the left hand side is fairly easy. for the right hand side I would say: $$\frac{2^k-3}{2^r}=\frac{2^k-2^a}{2^r}$$ where $a=\frac{\ln3}{\ln 2}\approx1.585$

Now you could say: $$\frac{2^k-2^a}{2^r}=2^{k-r}-2^{a-r}$$ noticing that for $r\ge2$ we have: $$\lceil2^{k-r}-2^{a-r}\rceil=\lceil2^{k-r}-1\rceil=2^{k-r}-1$$

---

I'm going to go back and have a look at where to go from here but it feels like the right direction

Answer 3

I am sorry but either the source is wrong or this was transcribed here incorrectly. Put $k=20$ and $n=2^k+3$ so $i=3$ and $i-1=2$ [allowed by the OP]. Then $$\displaystyle\sum_{r=1}^k\ \Big\lceil\frac{i-1}{2^r}\Big\rceil \ = \ \sum_{r=1}^k \Big\lceil\frac{2}{2^r}\Big\rceil \ \ge k \ $$ $$> i-2-k, \ \text{for $i=4$ and $k=20$}.$$ Now one does have $$\displaystyle\sum_{r=1}^k\ \Big\lceil\frac{i-1}{2^r}\Big\rceil \quad \le \quad \displaystyle\sum_{r=1}^k\ \Big(1+\Big(\frac{i-1}{2^r}\Big)\Big)$$ $$= \ \displaystyle\sum_{r=1}^k 1 \ + \displaystyle\sum_{r=1}^k\Big(\frac{i-1}{2^r}\Big) \quad = \quad k \ + \ (i-1) -\frac{i-1}{2^k}.$$ To get your desired bound you would need $\frac{i-1}{2^k} > 2k+1$, which is impossible if $n-2^{k}$ is allowed to be so small.