9
$\begingroup$

I am doing tasks from Concrete Mathematics by Knuth, Graham, Patashnik for trainning, but there are a lot of really tricky sums like that:

Calculate sum $$S_n = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor $$

My idea

I had the idea to check when $$\frac{n}{2^k} < \frac{1}{2}$$ because then $$ \forall_{k_0 \le k} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor=0$$ It should be $$ k_0 = \log_2(2n) $$ but I don't know how it helps me with this task (because I need not only "stop moment" but also sum of considered elements

Book idea

Let $$S_n = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor $$ then $$ S_n-S_{n-1} = 1$$

and then solve this recursion. But I write $S_n - S_{n-1}$ and I don't see how it can be $1$ , especially that is an infinite sum.

$\endgroup$
3
$\begingroup$

Since $S_1=1$ try to prove that $S_n=n$ by induction. Note that if $n=2m$ is even $$\begin{align*} S_n=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor &=\sum_{k=1}^{\infty}\left\lfloor\frac{2m}{2^k}+\frac12\right\rfloor =\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac12\right\rfloor\\ &=\left\lfloor m+\frac12\right\rfloor +\sum_{k=2}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac12\right\rfloor\\ &=\left\lfloor m+\frac12\right\rfloor +\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k}}+\frac12\right\rfloor=m+S_m=m+m=n \end{align*}$$ On the other hand if $n=2m+1$, then $$\begin{align*} S_n=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor &=\sum_{k=1}^{\infty}\left\lfloor\frac{2m+1}{2^k}+\frac12\right\rfloor =\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac{1}{2^{k}}+\frac12\right\rfloor\\ &=\left\lfloor m+\frac12+\frac12\right\rfloor +\sum_{k=2}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac{1}{2^{k}}+\frac12\right\rfloor\\ &=m+1+\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k}}+\frac{1}{2^{k+1}}+\frac12\right\rfloor\\ &=m+1+S_m=m+1+m=n. \end{align*}$$ where it remains to show that for all $k\geq 1$, $$\left\lfloor\frac{m}{2^{k}}+\frac{1}{2^{k+1}}+\frac12\right\rfloor=\left\lfloor\frac{m}{2^{k}}+\frac12\right\rfloor.$$ Can you show this last step?

P.S. Actually $S_n$ is a finite sum. If $n<2^{N}$ then $\frac{n}{2^{N+1}}<\frac12$ and $\left\lfloor \frac{n}{2^{N+1}} + \frac12 \right\rfloor=0$. Hence $$S_n = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{2^k} + \frac12 \right\rfloor=\sum_{k=1}^{N} \left\lfloor \frac{n}{2^k} + \frac12 \right\rfloor.$$

$\endgroup$
  • $\begingroup$ It seems that $\frac{1}{2^{k+1}}$ doesn't matter there $\endgroup$ – VirtualUser Mar 6 at 17:59
  • $\begingroup$ I written that as $ \left \lfloor \frac{m+1/2}{2^{k}} \right \rfloor $ - it seem to be true but I am not sure how formal proof would be like $\endgroup$ – VirtualUser Mar 6 at 18:07
  • $\begingroup$ It suffices to show that for any integer $N$ if $\frac{m}{2^{k}}+\frac12<N$ then $\frac{m}{2^{k}}+\frac{1}{2^{k+1}}+\frac12<N$ or if $2m+2^k<2^{k+1}N$ then $2m+2^k+1<2^{k+1}N$. Note that $2m+2^k$ and $2^{k+1}N$ are even numbers. $\endgroup$ – Robert Z Mar 6 at 18:31
  • $\begingroup$ Ahh, yes. So if in both sides of inequality $ 2m+2^k<2^{k+1}N $ we have even numbers, so add $1$ change nothing because a difference is at least $2$. Thanks! $\endgroup$ – VirtualUser Mar 6 at 18:40
  • $\begingroup$ @VirtualUser Yes, you are correct! $\endgroup$ – Robert Z Mar 6 at 18:42
3
$\begingroup$

Here we use a technique which is introduced in section 3.2 Floor/Ceiling Applications of OPs referred book Concrete Mathematics by R. L. Graham, D. E. Knuth and O. Patashnik. We show the following is valid for $n\in\mathbb{Z}, n>0$: \begin{align*} \color{blue}{\sum_{k=1}^\infty\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor=n}\tag{1} \end{align*}

Let $n=\sum_{j=0}^Na_j2^j$ be the binary representation of $n$ with $a_j\in\{0,1\}, 0\leq j\leq N$. We obtain \begin{align*} \color{blue}{\sum_{k=1}^\infty}\color{blue}{\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor} &=\sum_{k=1}^\infty\sum_{m=1}^\infty m\left[m=\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor\right]\tag{2}\\ &=\sum_{k=1}^\infty\sum_{m=1}^\infty m\left[m\leq \frac{n}{2^k}+\frac{1}{2}<m+1\right]\tag{3}\\ &=\sum_{k=1}^\infty\sum_{m=1}^\infty m\left[m-\frac{1}{2}\leq\frac{1}{2^k}\sum_{j=0}^Na_j2^j<m+\frac{1}{2}\right]\tag{4}\\ &=\sum_{j=0}^Na_j\sum_{k=1}^{j+1}\sum_{m=1}^\infty m\left[m-\frac{1}{2}\leq 2^{j-k}<m+\frac{1}{2}\right]\tag{5}\\ &=\sum_{j=0}^Na_j\left(\sum_{k=1}^j2^{j-k}+1\right)\tag{6}\\ &=\sum_{j=0}^N a_j\left(\sum_{k=0}^{j-1}2^k+1\right)\tag{7}\\ &=\sum_{j=0}^Na_j 2^j\tag{8}\\ &\,\,\color{blue}{=n} \end{align*} and the claim (1) follows.

Comment:

  • In (2) we introduce a series summing over $m$ and use Iverson brackets to get rid of the floor-function. Note the smallest value which might contribute to the sum is $m=1$.

  • In (3) we use an equivalent representation of the floor function.

  • In (4) we rearrange the inequality chain inside the Iverson brackets and use the binary representation of $n$.

  • In (5) we use the linearity of the $\sum$ operator. We also restrict the upper limit of the second left-most sum with $k=j+1$ since other values of $k$ do not contribute.

  • In (6) we observe that $m$ takes the value $2^{j-k}$ iff $1\leq k\leq j$ and $m=1$ if $k=j+1$.

  • In (7) we shift the index by one to start with $k=0$ and we also change to order of summation $k\to j-1-k$.

  • In (8) we use the finite geometric series formula $\sum_{k=0}^{j-1}2^k=\frac{2^j-1}{2-1}=2^j-1$ and get the binary representation of $n$.

$\endgroup$
2
$\begingroup$

Consider how $\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ depends on the binary representation of $n$. Dividing by $2^k$ shifts the digits to the right by $k$. There are then two cases:

  • If the $k^{th}$ binary digit of $n$ is $0$, then adding $1/2$ will not cause a carry, so $\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ is just equal to the truncation of $n/2^k$ after the decimal point.

  • If the $k^{th}$ binary digit of $n$ is $1$, then adding $1/2$ will cause a carry, so $\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ is just equal to this truncation plus one.

Now, letting $f_k(n)=\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ for brevity, consider the difference between $f_k(n)$ and $f_k(n-1)$. The difference between the binary representations of $n$ and $n-1$ is summarized as follows; if $n$ has $t$ trailing zeroes, then $n$ ends with $100\dots0$, while $n-1$ ends with $011\dots1$. Otherwise, the representations are the same.

  • If $k>t+1$, then $f_k(n)=f_k(n-1)$, since the binary representations of $n$ and $n-1$ are equal after the first $t+1$ places, and the first $t+1$ places do not affect the computation of $f_k(n)$ and $f_k(n-1)$.

  • If $k=t+1$, then $f_k(n)=f_k(n-1)+1$. The former has a carry, while the latter does not.

  • If $k<t+1$, then $f_k(n)=f_k(n-1)$. The latter will have a carry, and the former will not. You can verify this on your own with some examples.

Therefore, in

$$ S_n-S_{n-1}=\sum_{k=1}^\infty \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor-\left\lfloor \frac{n-1}{2^k} + \frac{1}{2} \right\rfloor $$ exactly one summand is equal to $1$ and the rest are zero, so $S_n-S_{n-1}=1$.

$\endgroup$
2
$\begingroup$

Let

$$2^{b}\le n<2^{b+1}$$

For all $1\le k\le b$,

$$\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor=\frac{2^b}{2^k}+\left\lfloor\frac{n-2^b}{2^k}+\frac12\right\rfloor.$$

For $k=b+1$,

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

And for $k>b+1$,

$$\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor=0.$$

This allows us to write, by summing,

$$S_n=2^{b-1}+2^{b-2}+\cdots 2^0+1+S_{n-2^b}=2^b+S_{n-2^b},$$

which shows that $n$ and $S_n$ share the same binary representation.

E.g., inductively,

$$S_{123}=64+S_{59}=64+32+S_{27}=64+32+16+S_{11}\\\cdots\\=64+32+16+8+2+1.$$

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