2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Gilding the lily to add my answer, so I will just say that the guiding principle to this problem is that if $a,b \in \Bbb{Z^+}$ then $$\left\lceil \frac{a}{b}\right\rceil ~-~ \frac{a}{b} \leq \frac{b-1}{b} = 1 - \frac{1}{b}.$$ $\endgroup$ Apr 27, 2022 at 0:32
  • $\begingroup$ @user2661923 Huh, I doesn't quite get it... $\endgroup$
    – Uduru
    Apr 27, 2022 at 2:42
  • $\begingroup$ For visualization purposes, use a concrete example. Suppose that $b = 17$ and let $r$ denote the smallest non-negative residue of $a, \pmod{17}.$ So, $r \in \{0,1,2,\cdots,16\}.$ $$\text{Let} ~f(a) = \left\lceil \frac{a}{b}\right\rceil - \frac{a}{b}.$$ If $r = 0,$ then $f(a) = 0.$ Otherwise, $$f(a) = \frac{17-r}{b}.$$ $\endgroup$ Apr 27, 2022 at 2:48
  • 1
    $\begingroup$ Difficult to answer, because, according to the other responses to this question, the assertion (as is) seems to be false. From my perspective, that is neither here nor there. That is, regardless of whether the assertion as is is true, or whether you or the problem composer made a mistake with the assertion, it is obvious what the problem composer must have intended : ...see next comment $\endgroup$ Apr 27, 2022 at 5:58
  • 1
    $\begingroup$ $\displaystyle \sum_{r=1}^k \frac{a}{2^r} = a - \frac{a}{2^k}.~~$ Also, $$\sum_{r=1}^k \left(\left\lceil\frac{a}{2^r}\right\rceil ~-~ \frac{a}{2^r}\right)$$ $$\leq ~ \left[\left(1 - \frac{1}{2}\right) + \left(1 - \frac{1}{2^2}\right) + \cdots + \left(1 - \frac{1}{2^k}\right)\right]$$ $$= ~k - \left[\left(\frac{1}{2} + \frac{1}{2^2} + \cdots + \frac{1}{2^k}\right) \right]$$ $$= ~k - \left[1 - \frac{1}{2^k}\right].$$ Whatever the true assertion turns out to be, I am confident that the above analysis will be pertinent. $\endgroup$ Apr 27, 2022 at 6:19

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I made a mistake there. The RHS should be $i-2+k$, not subtracting $k$. I'm very sorry. $\endgroup$
    – Uduru
    Apr 26, 2022 at 23:29
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .