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.
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} $$
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$:
$$\left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor = 1 + \sum_{i=(k+1), \ldots} \frac{a_i2^i}{2^{k+1}}$$
$$\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:
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$$
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.
