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.
 A: The statement is trivially true for $n=1$ and $n=2$. Suppose it is true for any positive integer less than $n$, and let's prove it is true for $n$. We have two cases:
$n=2m$ is even. Then:
$$
\begin{array}{cll}&\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\\=&
\left\lfloor \frac{2m+1}{2} \right\rfloor + \left\lfloor \frac{2m+2}{2^2} \right\rfloor + \left\lfloor \frac{2m+2^2}{2^3} \right\rfloor + \cdots + \left\lfloor \frac{2m+2^k}{2^{k+1}} \right\rfloor + \cdots
\\=&
m + \left(\left\lfloor \frac{m+1}{2} \right\rfloor + \left\lfloor \frac{m+2}{2^2} \right\rfloor + \cdots + \left\lfloor \frac{m+2^{k-1}}{2^k} \right\rfloor + \cdots\right)\\=& m + m &\text{ (inductive hypothesis)}\\ =&2m\\=&n\end{array}
$$
$n=2m+1$ is odd. This case is only slightly more complicated:
$$
\begin{array}{cll}&\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\\=&
\left\lfloor \frac{2m+2}{2} \right\rfloor + \left\lfloor \frac{2m+2+1}{2^2} \right\rfloor + \left\lfloor \frac{2m+2^2+1}{2^3} \right\rfloor + \cdots + \left\lfloor \frac{2m+2^k+1}{2^{k+1}} \right\rfloor + \cdots
\\ =&
(m + 1) + \left(\left\lfloor \frac{m+1+1/2}{2} \right\rfloor + \left\lfloor \frac{m+2+1/2}{2^2} \right\rfloor + \cdots + \left\lfloor \frac{m+2^{k-1}+1/2}{2^k} \right\rfloor + \cdots\right)\\
\\ =&
(m + 1) + \left(\left\lfloor \frac{m+1}{2} \right\rfloor + \left\lfloor \frac{m+2}{2^2} \right\rfloor + \cdots + \left\lfloor \frac{m+2^{k-1}}{2^k} \right\rfloor + \cdots\right)&\text{ the additional }1/2\text{ does not change anything}\\=& m+1 + m&\text{ (inductive hypothesis)}\\ =&2m+1\\=&n\end{array}
$$
A: Consider the binary representation of $n$:
$$n = \sum_{i=0,1,\ldots} a_i 2^i,\quad a_i\in\{0, 1\}$$
Consider the $k$th term of the sum (the term that adds to the $k$th bit and truncate), depending on whether the $k$th bit $a_k$ is $0$ or $1$:

*

*$a_k=1$ means the addition leads to a carry:

$$\left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor = 1 + \sum_{i=(k+1), \ldots} \frac{a_i2^i}{2^{k+1}}$$

*

*While for $a_k = 0$, there's no carry and the term is just a truncation:

$$\left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor = \sum_{i=(k+1), \ldots} \frac{a_i2^i}{2^{k+1}}$$
Either case,
$$\left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor = a_k + \sum_{i=(k+1), \ldots}a_i2^{i-(k+1)}$$
Then consider the whole series with terms in the above form, the $i$th bit $a_i$ appears in:

*

*Terms $0\le k < i$, $\left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor$ contributes $a_i2^{i-(k+1)}$ to the whole series;

*

*(or none if $i=0$, i.e. no less-significant bits;)



*Term $k = i$, $\left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor$ contributes $a_i$ to the whole series;

*Terms $k > i$, bit $a_i$ is truncated and has no effects on those terms.

The overall contribution of a bit $a_i$ on the whole series is the additional
$$\left(a_i2^{i-1} + a_i2^{i-2} + \ldots + a_i2^0\right) + a_i = a_i2^i$$
And the overall contribution of all bits $a_0, a_1, \ldots$ is
$$\sum_{i=0,\ldots} a_i2^i = n$$
A: 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.
