sum of floor function simplification 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.

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.
