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

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.

5 Answers

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

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

• It seems that $\frac{1}{2^{k+1}}$ doesn't matter there
– user617243
Mar 6, 2019 at 17:59
• 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
– user617243
Mar 6, 2019 at 18:07
• 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. Mar 6, 2019 at 18:31
• 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!
– user617243
Mar 6, 2019 at 18:40
• @VirtualUser Yes, you are correct! Mar 6, 2019 at 18:42

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

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

From $$\left\lfloor x+\frac{1}{2}\right\rfloor=\lfloor 2x\rfloor-\lfloor x\rfloor$$ we have

$$\left\lfloor \frac{n}{2^k}+\frac{1}{2}\right\rfloor=\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lfloor \frac{n}{2^k}\right\rfloor$$ therefore $$\sum_{k=1}^\infty \left\lfloor \frac{n}{2^k}+\frac{1}{2}\right\rfloor=\sum_{k=1}^\infty \left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lfloor \frac{n}{2^k}\right\rfloor\\ =\lfloor n\rfloor -\lim_{k\to \infty}\left\lfloor \frac{n}{2^k}\right\rfloor\\=n$$