Proving $\sum\limits_{k=0}^{\infty} \left\lfloor\frac{n+2^k}{2^{k+1}}\right\rfloor=n$

Question

Find $f(n)$ for each natural number $n$, where $$f(n)=\sum_{k=0}^{\infty} \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor.$$

I tried with a few different small $n$, $f(n)$ seems to be $n$. But is there a way to formally prove it?

Answer 1

An easier theorem might be: for any natural number $n$ and any $0\le\alpha<1$, $$\sum_{k=0}^{\infty}\left\lfloor\frac{n+\alpha+2^k}{2^{k+1}}\right\rfloor=n$$ It's true for $n=0$ because $\alpha+2^k<2^{k+1}$ and for $n=1$ because $2\le1+\alpha+1<4$ but $1+\alpha+2^k<2^{k+1}$ for $k>0$. Then if true for all natural numbers up to $n$, $$\begin{align}\sum_{k=0}^{\infty}\left\lfloor\frac{2n+\alpha+2^k}{2^{k+1}}\right\rfloor&=\left\lfloor\frac{2n+\alpha+1}{2}\right\rfloor+\sum_{k=1}^{\infty}\left\lfloor\frac{2n+\alpha+2^k}{2^{k+1}}\right\rfloor\\ &=n+\sum_{k=0}^{\infty}\left\lfloor\frac{2n+\alpha+2^{k+1}}{2^{k+2}}\right\rfloor\\ &=n+\sum_{k=0}^{\infty}\left\lfloor\frac{n+\frac{\alpha}2+2^{k}}{2^{k+1}}\right\rfloor=n+n=2n\end{align}$$ And also $$\begin{align}\sum_{k=0}^{\infty}\left\lfloor\frac{2n+1+\alpha+2^k}{2^{k+1}}\right\rfloor&=\left\lfloor\frac{2n+1+\alpha+1}{2}\right\rfloor+\sum_{k=1}^{\infty}\left\lfloor\frac{2n+1+\alpha+2^k}{2^{k+1}}\right\rfloor\\ &=n+1+\sum_{k=0}^{\infty}\left\lfloor\frac{2n+1+\alpha+2^{k+1}}{2^{k+2}}\right\rfloor\\ &=n+1+\sum_{k=0}^{\infty}\left\lfloor\frac{n+\frac{1+\alpha}2+2^{k}}{2^{k+1}}\right\rfloor=n+1+n=2n+1\end{align}$$ So it follows that it's true for all natural numbers $n$ and all $0\le\alpha<1$.

Hopefully it's clear why I can make this assertion: build the binary representation of $n$ starting from the high bit to low bit and at each stage it can be seen that the growing number satisfies the conclusion of the theorem, starting from $1$ and ending at $n$.

Answer 2

Hint: Let $m$ be the integer such that $2^{m-1}\leq n<2^m.$ If $k>m$, then $n+2^k<2^m+2^k<2^k+2^k = 2^{k+1}.$ This means that $\left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor = 0,$ for $k>m.$ So you only need to consider the sum up to $m.$