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!


The first term in your infinite sum (calling it $S(n)$), using the identity, is

$$\left[n\right] - \left[\frac{n}{2}\right]$$

The next term is

$$\left[\frac{n}{2}\right] - \left[\frac{n}{4}\right]$$

The next term is

$$\left[\frac{n}{4}\right] - \left[\frac{n}{8}\right]$$

And so on. So then the partial sum out to the $m$th term, $S(n,m)$, is just $[n] - [n/2^m]$. Taking this as $m$ approaches infinity:

$$\lim_{m \to \infty}S(n, m) = \lim_{m \to \infty}\left(\left[n\right] - \left[\frac{n}{2^m}\right]\right) = \left[n\right] = n.$$

| cite | improve this answer | |
  • $\begingroup$ Edited my answer. $\endgroup$ – John Jun 10 '16 at 23:22
  • $\begingroup$ Thank you Sir. Sir I have one last doubt. You've written that $[x]=x$. However, in the original question it wasn't mentioned that $x\in Z$ only. So how can the result you've used be true? $\endgroup$ – user342209 Jun 10 '16 at 23:24
  • $\begingroup$ Or is it that the result holds true only when $n\in Z$? $\endgroup$ – user342209 Jun 10 '16 at 23:25
  • $\begingroup$ I saw that and changed everything to $n$ since that's what the original problem stated. When the variable is $n$ it usually means a whole number, and I did assume that in the last step. But ... you're right, it's an assumption. $\endgroup$ – John Jun 10 '16 at 23:26
  • $\begingroup$ Sir, I just checked another source and there it is mentioned that $n\in\Bbb Z^+$. Thanks a lot for your solution; I really really liked it! $\endgroup$ – user342209 Jun 10 '16 at 23:31

For $x=\frac{n}{2^k}$, the identity you have means:

$$\left\lfloor \frac{n}{2^k}\right\rfloor =\left \lfloor \frac{n}{2^{k+1}}\right\rfloor+\left\lfloor \frac{n+2^k}{2^{k+1}}\right\rfloor$$

So prove by induction for any $m\geq 0$ that:

$$ n = \left\lfloor\frac{n}{2^m}\right\rfloor+\sum_{k=0}^{m-1}\left\lfloor\frac{x+2^{k}}{2^{k+1}}\right\rfloor$$

The pick $m$ so that $2^m>n$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks Sir. Sir, is there any way other than Induction to proceed with the given hint? It's just that I'm very weak at proofs through Induction, and am quite sure I won't be able to do this one. $\endgroup$ – user342209 Jun 10 '16 at 23:13
  • $\begingroup$ Sir, is there any way to prove the proposition using the Squeeze Theorem? I was unable to select adequately tight bounds. Are there any other bounds which would work out? $\endgroup$ – user342209 Jun 11 '16 at 14:49

Let's start with the observation that, for any integers $a,b\gt0$,

$$\left\lfloor{a\over b}+{1\over2b}\right\rfloor=\left\lfloor{a\over b}\right\rfloor\quad(*)$$

Now define

$$f(n)=n-\left(\left\lfloor n+1\over2 \right\rfloor+\left\lfloor n+2\over4 \right\rfloor+\left\lfloor n+4\over8 \right\rfloor+\left\lfloor n+8\over16 \right\rfloor+\cdots \right)$$


$$\begin{align} f(2n) &=2n-\left(\left\lfloor 2n+1\over2 \right\rfloor+\left\lfloor 2n+2\over4 \right\rfloor+\left\lfloor 2n+4\over8 \right\rfloor+\left\lfloor 2n+8\over16 \right\rfloor+\cdots \right)\\ &=2n-\left(\left\lfloor n+{1\over2} \right\rfloor+\left\lfloor n+1\over2 \right\rfloor+\left\lfloor n+2\over4 \right\rfloor+\left\lfloor n+4\over8 \right\rfloor+\cdots \right)\\ &=2n-\left(n+\left\lfloor n+1\over2 \right\rfloor+\left\lfloor n+2\over4 \right\rfloor+\left\lfloor n+4\over8 \right\rfloor+\cdots \right)\\ &=f(n) \end{align}$$


$$\begin{align} f(2n+1) &=2n+1-\left(\left\lfloor 2n+2\over2 \right\rfloor+\left\lfloor 2n+3\over4 \right\rfloor+\left\lfloor 2n+5\over8 \right\rfloor+\left\lfloor 2n+9\over16 \right\rfloor+\cdots \right)\\ &=2n+1-\left(\left\lfloor n+1 \right\rfloor+\left\lfloor {n+1\over2}+{1\over4} \right\rfloor+\left\lfloor {n+2\over4}+{1\over8} \right\rfloor+\left\lfloor {n+4\over8}+{1\over16} \right\rfloor+\cdots \right)\\ &=2n+1-\left(n+1+\left\lfloor n+1\over2 \right\rfloor+\left\lfloor n+2\over4 \right\rfloor+\left\lfloor n+4\over8 \right\rfloor+\cdots \right)\quad\text{using (*)}\\ &=f(n) \end{align}$$

Consequently $f(n)$ is a constant function for all $n\gt0$, so it suffices to evaluate

$$\begin{align} f(1)&=1-\left(\left\lfloor 1+1\over2 \right\rfloor+\left\lfloor 1+2\over4 \right\rfloor+\left\lfloor 1+4\over8 \right\rfloor+\left\lfloor 1+8\over16 \right\rfloor+\cdots \right)\\ &=1-(1+0+0+0+\cdots)\\ &=0 \end{align}$$

| cite | improve this answer | |

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

| cite | improve this answer | |

Let $n=d_0+2d_1+4d_2+\dots+2^kd_k$, where $d_i\in\{0,1\}$, for each $i=0,\dots,k$.

Now, since $n-d_0$ is a multiple of $2$, $\left[\frac{n+1}2\right]=\left[\frac{n-d_0+d_1+1}2\right]=\frac{n-d_0}2+\left[\frac{d_0+1}2\right]$.

But let's have a look at $\left[\frac{d_0+1}2\right]$. If $d_0=0$, we have $[1/2]=0=d_0$. Otherwise, if d_0=1, we have $[2/2]=[1]=1=d_0$. So in either cases, it is equal to $d_0$.

So, $\left[\frac{n+1}2\right]=\frac{n-d_0}2+d_0$.

Now let's do for $\left[\frac{n+2^{i-1}}{2^i}\right]$, as we know $(n-d_0-\dots-2^{i-1}d_{i-1})$ is a multiple of $2^i$, so $$\left[\frac{n+2^{i-1}}{2^i}\right]=\left[\frac{(n-d_0-\dots-2^{i-1}d_{i-1})+d_0+\dots_+2^{i-1}d_{i-1}+2^{i-1}}{2^i}\right]\\ = \frac{n-d_0-\dots-2^{i-1}d_{i-1}}{2^i}+\left[\frac{d_0+\dots_+2^{i-1}d_{i-1}+2^{i-1}}{2^i}\right]\\ = \frac{n-d_0-\dots-2^{i-1}d_{i-1}}{2^i}+\left[\frac{2^{i-1}d_{i-1}+2^{i-1}}{2^i}\right]\\ = \frac{n-d_0-\dots-2^{i-1}d_{i-1}}{2^i}+d_{i-1}$$

so we can add up all these... so we have...




$=\frac{(2^{k-1}+\dots+1)n+(2^{k-1}-\dots-1)d_0+\dots+(2^{k-i}-\dots-2^{i-1})d_{i-1}+\dots+2^{k-1}d_k-1}{2^k}=\frac{(2^{k}-1)n+d_0+\dots+2^id_i+\dots 2^kd_k}{2^k}=\frac{(2^k-1)n+n}{2^k}=\frac{(2^k-1+1)n}{2^k}=\frac{(2^k)n}{2^k}=n$

| cite | improve this answer | |

Lets think binary, and instead of $n$, lets write (abcd) where $a$, $b$, $c$, and $d$ are its digits, a.k.a. bits. Here w.l.o.g. we supposed $n$ is 4 bit long.





$=abc+d+ab+c+(a+b+a)=abc+d+ab+c+(a0+b)$ $=abc+d+ab+c+ab$

$=abc+d+(ab+c+ab)=abc+d+abc=abc$. ☺

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.