How do we prove that $[n+1/2]+[n+2/4]+[n+4/8]+[n+8/16] ...=n$?

Question

Would someone please help me to prove the above relation? $[.]$ denotes the floor function $n$ is a positive integer.

Answer 1

Presumably $n$ is a positive integer and the equation should be written $$\lfloor(n + 1)/2\rfloor + \lfloor(n + 2)/4\rfloor + \lfloor(n + 4)/8\rfloor + \cdots = n.$$ Sketch proof by induction: Suppose it's true for $n = m - 1$. For the step to $n = m$, let $2^k$ be the highest power of $2$ that divides $m$. The term $\lfloor(n + 2^k)/2^{k+1}\rfloor$ will increase by $1$ and all the others will stay the same.