3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Hi , @math110 , can you please explain the last step , how did you get $2n$ ... would be grateful and thanks a ton :) $\endgroup$ – pranav Mar 24 '15 at 1:33
  • 1
    $\begingroup$ 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$$ $\endgroup$ – math110 Mar 24 '15 at 2:35
  • $\begingroup$ Thanks @math110 , I think that explains it :) $\endgroup$ – pranav Mar 24 '15 at 3:58
2
$\begingroup$

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.

$\endgroup$

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.