12
$\begingroup$

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!

$\endgroup$
0

6 Answers 6

9
$\begingroup$

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.$$

$\endgroup$
8
  • $\begingroup$ Edited my answer. $\endgroup$
    – John
    Jun 10, 2016 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, 2016 at 23:24
  • $\begingroup$ Or is it that the result holds true only when $n\in Z$? $\endgroup$
    – user342209
    Jun 10, 2016 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, 2016 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, 2016 at 23:31
6
$\begingroup$

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$.

$\endgroup$
2
  • 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, 2016 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, 2016 at 14:49
3
$\begingroup$

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)$$

Then

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

and

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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{n-d_0}2+d_0+\dots+\frac{n-d_0-\dots-2^{i-1}d_{i-1}}{2^i}+d_{i-1}+\dots+\frac{n-d_0-\dots-2^{k-1}d_{k-1}}{2^k}+d_{k-1}+\frac{n-d_0-\dots-2^{k}d_{k}}{2^{k+1}}+d_{k}$

$=\frac{n+d_0}2+\dots+\frac{n-d_0-\dots+2^{i-1}d_{i-1}}{2^i}+\dots+\frac{n-d_0-\dots+2^{k-1}d_{k-1}}{2^k}+\frac{n-d_0-\dots+2^{k}d_{k}}{2^{k+1}}$

$=\frac{2^{k-1}n+2^{k-1}d_0}{2^k}+\dots+\frac{n-d_0-\dots+2^{i-1}d_{i-1}}{2^i}+\dots+\frac{n-d_0-\dots+2^{k-1}d_{k-1}}{2^k}$

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

$\endgroup$
0
$\begingroup$

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.

$\lfloor\frac{abcd+1}{10}\rfloor+\lfloor\frac{abcd+10}{100}\rfloor+\lfloor\frac{abcd+100}{1000}\rfloor+\lfloor\frac{abcd+1000}{10000}\rfloor+\lfloor\frac{abcd+10000}{100000}\rfloor+\dots$

$=\lfloor\frac{abc0+d+1}{10}\rfloor+\lfloor\frac{ab00+cd+10}{100}\rfloor+\lfloor\frac{a000+bcd+100}{1000}\rfloor+\lfloor\frac{abcd+1000}{10000}\rfloor+\lfloor\frac{abcd+10000}{100000}\rfloor+\dots$

$=abc+\lfloor\frac{d+1}{10}\rfloor+ab+\lfloor\frac{cd+10}{100}\rfloor+a+\lfloor\frac{bcd+100}{1000}\rfloor+\lfloor\frac{abcd+1000}{10000}\rfloor+\lfloor\frac{abcd+10000}{100000}\rfloor+\dots$

$=abc+d+ab+c+a+b+a+0+\dots=abc+d+ab+c+a+b+a$

$=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$. ☺

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .