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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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