<s>[INST] 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.
 [/INST] 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}
$$
</s>