Number Theory : Show that $\sum_{i=0}^\infty$ $ [\frac{n}{2^i}+\frac{1}{2}]$ $=$ $2n$

Question

I was doing some basic Number Theory problems and came across this problem :

Show that for any integer $n$ $\geq$ $1$ ; $$\sum_{i=0}^\infty [\frac{n}{2^i}+\frac{1}{2}] = 2n$$ ; where $[x]$ represents the greatest integer / floor function

I am all thumbs , even a hint would suffice

P.S. In the book , this question is given in the section on the Greatest Integer Function , perhaps that might help . Also , this is not a homework question , I am just practicing number theory questions on my own from the book

Answer 1

You must first write $n$ in base $2$ that is :

$$n=\sum_{k=0}^da_k2^k $$

with $a_k=0$ or $1$ and $a_d=1$. Then you have that :

$$\frac{n}{2^i}+\frac{1}{2}=\sum_{k=0}^{i-2}a_k2^{k-i}+a_{i-1}\frac{1}{2}+\frac{1}{2}+\sum_{k=i}^da_k2^{k-i} $$

You then see that :

$$[\frac{n}{2^i}+\frac{1}{2}]=[\sum_{k=0}^{i-2}a_k2^{k-i}+a_{i-1}\frac{1}{2}+\frac{1}{2}]+\sum_{k=i}^da_k2^{k-i} $$

Now, if $a_{i-1}=0$ then :

$$\sum_{k=0}^{i-2}a_k2^{k-i}+0\frac{1}{2}+\frac{1}{2}<1$$

So :

$$[\frac{n}{2^i}+\frac{1}{2}]=a_{i-1}+\sum_{k=i}^da_k2^{k-i} $$

if $a_{i-1}=1$ then :

$$1\leq\sum_{k=0}^{i-2}a_k2^{k-i}+1\frac{1}{2}+\frac{1}{2}<2$$

So :

$$[\frac{n}{2^i}+\frac{1}{2}]=a_{i-1}+\sum_{k=i}^da_k2^{k-i} $$

In both case you have that :

$$[\frac{n}{2^i}+\frac{1}{2}]=a_{i-1}+\sum_{k=i}^da_k2^{k-i} $$

If you sum up the whole thing for $i$ from $1$ to $d+1$ :

$$\sum_{i=1}^{d+1}[\frac{n}{2^i}+\frac{1}{2}]=\sum_{i=1}^{d+1}a_{i-1}+\sum_{i=1}^{d+1}\sum_{k=i}^da_k2^{k-i}=\sum_{i=0}^{d}a_i+\sum_{i=1}^{d+1}\sum_{k=i}^da_k2^{k-i}$$

$$\sum_{i=1}^{d+1}\sum_{k=i}^da_k2^{k-i}=\sum_{i=1}^{d}\sum_{k=i}^da_k2^{k-i}$$

$$\sum_{i=1}^{d+1}\sum_{k=i}^da_k2^{k-i}=\sum_{k=1}^{d}a_k\sum_{i=1}^k2^{k-i}$$

$$\sum_{i=1}^{d+1}\sum_{k=i}^da_k2^{k-i}=\sum_{k=1}^{d}a_k\sum_{i=0}^{k-1}2^{i}$$

$$\sum_{i=1}^{d+1}\sum_{k=i}^da_k2^{k-i}=\sum_{k=1}^{d}a_k(2^k-1)$$

Finally :

$$\sum_{i=1}^{d+1}[\frac{n}{2^i}+\frac{1}{2}]=\sum_{i=0}^{d}a_i+\sum_{k=1}^{d}a_k(2^k-1)=\sum_{k=0}^da_k=n$$

Now it suffices to remark that if $i>d+1$ then :

$$[\frac{n}{2^i}+\frac{1}{2}]=0$$

to conclude.

Answer 2

use this Hermit identity $$[x]+[x+\dfrac{1}{2}]=[2x]\Longrightarrow [x+\dfrac{1}{2}]=[2x]-[x]$$ so $$[\dfrac{n}{2^i}+\dfrac{1}{2}]=[\dfrac{n}{2^{i-1}}]-[\dfrac{n}{2^i}]$$ so $$\sum_{i=0}^{\infty}[\dfrac{n}{2^i}+\dfrac{1}{2}]=n+\sum_{i=1}^{\infty}\left([\dfrac{n}{2^{i-1}}]-[\dfrac{n}{2^i}]\right)=2n$$