<s>[INST] Proving $\sum\limits_{k=0}^{\infty} \left\lfloor\frac{n+2^k}{2^{k+1}}\right\rfloor=n$ 
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?
 [/INST] 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$.
</s>