sum of floor function simplification

Question

Let $n \in \mathbb{N}$.

I'm trying to show $\sum_{i=1}^{\infty} \left(\left \lfloor{\frac{n+2^k-1}{2^i}}\right \rfloor - \left \lfloor{\frac{n-1}{2^i}}\right \rfloor \right) = 2^k-1$.

I know that when $2^i > n-1$, the right floor function will become zero.

I'm not sure how I cancel out the $n$'s.

I also tried solving the sum of each floor function separately, but didn't get anywhere.

Any suggestions will be appreciated!

Thanks.

Answer 1

What you're trying to show is not always true. For example, let $n = 4$, so $n - 1 = 3$, and $k = 1$, so $2^k = 2$. This means $n + 2^k - 1 = 5$. However, using that each summation term is non-negative, the first few terms then become

$$\begin{equation}\begin{aligned} & \sum_{i=1}^{\infty} \left(\left\lfloor{\frac{n+2^k-1}{2^i}}\right\rfloor - \left\lfloor{\frac{n-1}{2^i}}\right\rfloor\right) \\ & = \left(\left\lfloor\frac{5}{2}\right\rfloor - \left\lfloor\frac{3}{2}\right\rfloor\right) + \left(\left\lfloor\frac{5}{4}\right\rfloor - \left\lfloor\frac{3}{4}\right\rfloor\right) + \ldots \\ & = (2 - 1) + (1 - 0) + \ldots \\ & = 1 + 1 + \ldots \\ & = 2 \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Note I've used that all of the remaining terms, i.e., the "$\ldots$" part, are $0$. This is larger than your right side of $2^{k} - 1 = 1$.

Note your statement would be correct with an appropriate restriction between $k$ and $n$. In particular, something like $2^k \gt n - 1$ works. This is because, for $i \le k$, each of the summation terms becomes

$$\begin{equation}\begin{aligned} \left\lfloor{\frac{n+2^k-1}{2^i}}\right\rfloor - \left\lfloor{\frac{n-1}{2^i}}\right\rfloor & = \left(\left\lfloor{\frac{2^k}{2^i} + \frac{n-1}{2^i}}\right\rfloor\right) - \left\lfloor{\frac{n-1}{2^i}}\right\rfloor \\ & = \left(2^{k-i} + \left\lfloor{\frac{n-1}{2^i}}\right\rfloor\right) - \left\lfloor{\frac{n-1}{2^i}}\right\rfloor \\ & = 2^{k-i} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

For $i \gt k$, then $2^i \ge 2(2^k) \gt n + 2^k - 1$ and $2^i \gt n - 1$, so both floor terms become $0$. Thus, the total sum would be that of a geometric series of

$$\sum_{i=1}^{k}(2^{k-i}) = 2^k - 1 \tag{3}\label{eq3A}$$

which then matches your right side.

Answer 2

The point is that the LHS is a geometric series, because extraneous parts of the sums cancel. However, the result doesn't seem quite right, because you get some extra terms.

$$ \begin{align} &\sum_{i=1}^{\infty} \left( \left\lfloor{\frac{n+2^k-1}{2^i}}\right \rfloor - \left \lfloor{\frac{n-1}{2^i}} \right\rfloor \right)\\ &= \sum_{i=1}^{k} \left( \left\lfloor{\frac{n+2^k-1}{2^i}}\right \rfloor - \left \lfloor{\frac{n-1}{2^i}} \right\rfloor \right) +\sum_{i=k+1}^{\infty} \left( \left\lfloor{\frac{n+2^k-1}{2^i}}\right \rfloor - \left \lfloor{\frac{n-1}{2^i}} \right\rfloor \right)\\ &= \sum_{i=1}^{k} \left( \frac{2^k}{2^i} +\left\lfloor{\frac{n-1}{2^i}}\right \rfloor - \left \lfloor{\frac{n-1}{2^i}} \right\rfloor \right) +\sum_{i=k+1}^{\infty} \mathbb{1}(n-1<2^i, n+2^k-1\ge 2^i)\\ &= \sum_{i=1}^{k}2^{k-i}+ \text{something}\\ &= \sum_{j=0}^{k-1}2^j + \text{something}\\ &= 2^k-1 + \text{something} \end{align} $$