How to prove this summation of floor function I am supposed to show that
$$
\left\lfloor \frac{n+1}{2} \right\rfloor + \left\lfloor \frac{n+2}{2^2} \right\rfloor + \left\lfloor \frac{n+2^2}{2^3} \right\rfloor + \cdots + \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor + \cdots = n
$$
For all postive integers $n \geq 1 $. (Note that this summation is not infinite, since $0 < \frac{n+2^k}{2^{k+1}} < 1$ for large $k$.
I can't seem to find a good way to tackle this exercise.

So the first idea is to consider the base 2 expansion of $n$ (this is natural because you have the power of 2 everywhere). We then write
$$
n=\sum_{k=\geq 0} a_k 2^k, \quad a_k\in\{0,1\}
$$
Then we can actually compute each of the terms in your sum:
$$
\lfloor \frac{n+2^s}{2^{s+1}}\rfloor=\lfloor \sum_k (a_k +\delta_{k,s})2^{k-(s+1)}\rfloor=\sum_{k\geq s+1} a_k 2^{k-(s+1)}+\lfloor \frac{a_s+1}{2}+\sum_{k< s} a_k 2^{k-(s+1)}\rfloor
$$
The last sum inside the floor function can be bounded by:
$$
\sum_{k< s} a_k 2^{k-(s+1)}\leq \frac{1}{2^{s+1}}\sum_{k<s} 2^k=\frac{1}{2^{s+1}}\frac{2^{s}-1}{2-1}=\frac{1}{2}-\frac{1}{2^{s+1}}<\frac{1}{2}
$$
Then we can just notice that if $a_s=0$ the whole term inside the floor function gives $1/2+\sum \dots<1/2+1/2$ hence the floor will be $0$. Similarly if $a_s=1$ one gets that the floor term is $1$ hence we simply have.
$$
\lfloor \frac{n+2^s}{2^{s+1}}\rfloor=\sum_{k\geq s+1} a_k 2^{k-(s+1)}+a_s
$$
Now the results follows from taking the sum over s, reversing the order of summation and using the geometric series (as I did above). I will leave you fill the details.
