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

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

• S_k>k/2? limit goes infinity.. – vudu vucu Mar 23 '15 at 14:14
• Typo? The term $i=0$ gives $n$. – André Nicolas Mar 23 '15 at 14:21
• what is the typo @AndréNicolas , I will correct it ... – pranav Mar 23 '15 at 14:23
• Still waiting for a response ... – pranav Mar 23 '15 at 15:15
• I think typo is the start of index, it should start at $1$ instead of $0$ – ganeshie8 Mar 23 '15 at 15:19

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

• Hi , @math110 , can you please explain the last step , how did you get $2n$ ... would be grateful and thanks a ton :) – pranav Mar 24 '15 at 1:33
• because $$\sum_{i=1}^{\infty}\left([\dfrac{n}{2^{i-1}}]-[\dfrac{n}{2^i}]\right)=n-\lim_{N\to \infty}[\dfrac{n}{2^N}]=n$$ – math110 Mar 24 '15 at 2:35
• Thanks @math110 , I think that explains it :) – pranav Mar 24 '15 at 3:58

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.