I have been messing around analyzing some self-made algorithms and then I stumbled upon this summation:
$$\sum_{j=0}^{n}\left\lfloor{2^{i-j}}\right\rfloor$$
I am thinking that my common algebraic manipulations involving series won't apply because of the floor function.
I also tried entering this series in wolframalpha but no luck.
Does anyone know how to do this?
On
Assuming that $i \in \mathbb{Z}$ and $n \in \mathbb{N}$, observe that as long as $j \leq i$ you have a normal summation, while in the other case, $0 \leq 2^k < 1$ for any $k < 0$. To deal with $i < 0$ we use $i' = \max(i,-1)$. Then we get:
\begin{align*} \sum_{j = 0}^{n} \lfloor 2^{i-j} \rfloor &= \sum_{j=0}^{\max(i,-1)} \lfloor 2^{i-j} \rfloor + \sum_{j=\max(i+1,0)}^{\max(n,i)} \lfloor 2^{i-j} \rfloor \\ &= \sum_{j=0}^{\max(i,-1)} 2^{i-j} + \sum_{j=\max(i+1,0)}^{\max(n,i)} \lfloor 2^{i-j} \rfloor \\ &= \sum_{k=0}^{\max(i,-1)} 2^k + \sum_{j=\max(i+1,0)}^{\max(n,i)} 0 \\ &= 2^{\max(i,-1)+1} -1 + 0 \\ &= 2^{\max(i+1,0)} - 1 \end{align*}
I hope this helps $\ddot\smile$
Irrespective of the value of $i $, whether it is or not greater than $j $, we can write our sum as: $$S = \sum_{j=0}^{i} \lfloor 2^{i-j} \rfloor + \sum_{j=i+1}^{n} \lfloor 2^{i-j} \rfloor$$
Case $1$: If $i \geq n $, $$S = \sum_{j=0}^{n} \lfloor 2^{i-j} \rfloor = \sum_{j=0}^{n} 2^{i-j} (\text {why ?}) $$
Case $2$: If $i < n $, $$S = \sum_{j=0}^{i} \lfloor 2^{i-j} \rfloor + \sum_{j=i+1}^{n} \lfloor 2^{i-j} \rfloor$$ $$= \sum_{j=0}^{i} \lfloor 2^{i-j} \rfloor + 0 (\text {why?})$$ $$= \sum_{j=0}^{i} 2^{i-j}$$
The final result in both cases is an easily simplifiable geometric series. Hope it helps.