1
$\begingroup$

Show that $$\sum_{i=1}^{n} \left\lceil\log_{2}\frac{2n}{2i-1}\right\rceil=2n -1 $$ where $ \lceil\cdot\rceil$ denotes the ceiling function.

My method: one way would be observe each part of the summation is telling numbers of form $2^\alpha k$ where $k$ is any odd number (from the list of numbers from $2$ to $2n$).

But I would like to know whether there is an algebraic proof, or maybe some bit of number theory that will help solve it.

$\endgroup$
12
  • $\begingroup$ Is this true? If $n=2$ the left hand is $\big \lfloor \log_2 \frac {4}{1}\big \rfloor + \big \lfloor \log_2 \frac {4}{3}\big \rfloor=2$ not $3$. $\endgroup$
    – lulu
    Commented Sep 5, 2022 at 11:39
  • $\begingroup$ Oh i am sorry i am editing it a bit $\endgroup$
    – ProblemDestroyer
    Commented Sep 5, 2022 at 11:41
  • $\begingroup$ Now i think least integer function should rectify it @lulu $\endgroup$
    – ProblemDestroyer
    Commented Sep 5, 2022 at 11:42
  • $\begingroup$ Oh, you are using the ceiling function? That's very non-standard notation. You used the old notation for the floor function. I suggest editing to use the standard notation for the ceiling function, \lceil $\cdots$ \rceil $\endgroup$
    – lulu
    Commented Sep 5, 2022 at 11:44
  • 1
    $\begingroup$ Nice thanks for those @JohnOmielan $\endgroup$
    – ProblemDestroyer
    Commented Sep 6, 2022 at 1:00

1 Answer 1

Reset to default
2
$\begingroup$

You can prove it by induction. The first observation is: $$\left\lceil\log_{2}\frac{2n}{2i-1}\right\rceil = 1 + \left\lceil\log_{2}\frac{n}{2i-1}\right\rceil$$

So it suffices to prove $\sum_{i=1}^{n} \left\lceil\log_{2}\frac{n}{2i-1}\right\rceil = n-1$. The next observation is that the latter half of the sum is zero (when $2i - 1 > n$, we have $\frac{n}{2i-1} \in (\frac 12, 1)$). Formally:

$n=2k$:

$$\sum_{i=1}^{2k} \left\lceil\log_{2}\frac{2k}{2i-1}\right\rceil = \sum_{i=1}^{k} \left\lceil\log_{2}\frac{2k}{2i-1}\right\rceil + 0,$$

which by induction hypothesis is $2k-1 = n - 1$.

$n=2k + 1$:

$$\sum_{i=1}^{2k} \left\lceil\log_{2}\frac{2k + 1}{2i-1}\right\rceil = \sum_{i=1}^{k + 1} \left\lceil\log_{2}\frac{2k + 1}{2i-1}\right\rceil + 0 = 1 + \sum_{i=1}^{k} \left\lceil\log_{2}\frac{2k + 1}{2i-1}\right\rceil.$$

We want to show that $\sum_{i=1}^{k} \left\lceil\log_{2}\frac{2k + 1}{2i-1}\right\rceil = (n - 1) - 1 = 2k$. By the induction hypothesis, we know that $\sum_{i=1}^{k} \left\lceil\log_{2}\frac{2k}{2i-1}\right\rceil = 2k - 1$. Let's compare them term by term, i.e. $\left\lceil\log_{2}\frac{2k}{2i-1}\right\rceil$ vs $\left\lceil\log_{2}\frac{2k + 1}{2i-1}\right\rceil$.

Let's fix $i$, and let $\ell$ be the smallest integer such that $2^\ell \ge \frac{2k}{2i-1}$. When is it not the case that $2^\ell \ge \frac{2k + 1}{2i - 1}$? It happens iff $\frac{2k}{2i - 1}$ is a power of two. This happens for exactly on term: for $i$ such that $2k = (2i - 1) \cdot 2^t$ for some $t$. Hence, $$\sum_{i=1}^{k} \left\lceil\log_{2}\frac{2k + 1}{2i-1}\right\rceil = 1 +\sum_{i=1}^k \left\lceil\log_{2}\frac{2k}{2i-1}\right\rceil = 2k$$

$\endgroup$

You must log in to answer this question.

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