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.

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}
$$
