<s>[INST] Prove that $\lfloor\frac{n+1}{2}\rfloor+\lfloor\frac{n+2}{4}\rfloor+\lfloor\frac{n+4}{8}\rfloor+\lfloor\frac{n+8}{16}\rfloor+ \dots=n$ 
Prove $$\left[\dfrac{n+1}{2}\right]+\left[\dfrac{n+2}{4}\right]+\left[\dfrac{n+4}{8}\right]+\left[\dfrac{n+8}{16}\right] + \dots=n$$ 
  where $[x]=\lfloor x\rfloor$

$$$$
It was suggested that somehow I use the identity $[x]=\left[\dfrac x2\right]+\left[\dfrac{x+1}{2}\right]$$$$$After struggling for a while, I realised I wasn't getting anywhere using his hint, probably because I couldn't really understand how I was to use it. Instead I tried to use the Squeeze Theorem by rewriting the $nth$ term of the series (referred to later as S) as$$$$ $$t_n=\left[\dfrac{n+2^k}{2^{k+1}}\right] \text{ where } 0\le k<\infty$$
$$\Rightarrow \dfrac{n+2^k}{2^{k+1}}-1<\left[\dfrac{n+2^k}{2^{k+1}}\right]\le \dfrac{n+2^k}{2^{k+1}}$$
$$$$
$$ \lim_{k\to \infty}(k+1)\left(\dfrac{n+2^k}{2^{k+1}}-1\right)<S\le  \lim_{k\to \infty}(k+1)\left( \dfrac{n+2^k}{2^{k+1}}\right)$$
However these bounds are too loose as the limits diverge to $-\infty$ and $\infty$ respectively.
$$$$
Could somebody please show me how to prove the series is equal to $n$, either through the given hint, or through the selection of tighter bounds for the Squeeze Theorem? Many thanks!
 [/INST] $$\begin{align}
\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\left[ \frac{x+1}2\right]&=\left[x\right]-\left[\frac x2\right]\end{align}$$
Put $x=\dfrac n{2^r}$:
$$\begin{align}
\left[ \frac{\frac n{2^r}+1}2\right]&=\left[\frac n{2^r}\right]-\left[\frac {\frac n{2^r}}2\right]\\
\left[\frac{n+2^r}{2^{r+1}}\right]&=\left[\frac n{2^r}\right]-\left[\frac n{2^{r+1}}\right]\\
r=0:\qquad \left[\frac{n+1}{2}\right]&=\;\left[n\right]\;-\left[\frac n{2}\right]\\
r=1:\qquad \left[\frac{n+2}{4}\right]&=\left[\frac n{2}\right]-\left[\frac n{4}\right]\\
r=2:\qquad \left[\frac{n+4}{4}\right]&=\left[\frac n{4}\right]-\left[\frac n{8}\right]\\
r=3:\qquad \left[\frac{n+8}{16}\right]&=\left[\frac n{8}\right]-\left[\frac n{16}\right]\\
&\vdots\\
&\vdots\\
\text{Summing:}
\left[\dfrac{n+1}{2}\right]+\left[\dfrac{n+2}{4}\right]+\left[\dfrac{n+4}{8}\right]+\left[\dfrac{n+8}{16}\right] + \dots&=\left[n\right]\\
&=n\qquad\blacksquare
\end{align}$$
</s>