Prove for every $n,\;\;$ $\sum\limits_{k=1}^{\infty}\left\lfloor \frac{n}{2^{k}}+\frac{1}{2} \right\rfloor=n $

Question

Problem Prove that for every nonnegative integer $n$ we have, $$\sum_{k=1}^{\infty}\left\lfloor \frac{n}{2^{k}}+\frac{1}{2} \right\rfloor=n$$ where $\lfloor x\rfloor$ denotes the integer part of $x.$ Please give me a hint. Even, I don't know how to start.

Answer 1

Every nonnegative integer $n$ has a unique binary representation $n = \sum_{k=0}^{\ell} a_k 2^k$ where each $a_k \in \{0,1\}$. We have $$\frac{n}{2^j} = \sum_{k=0}^{\ell} a_k 2^{k-j} = \frac{a_0}{2^j} + \frac{a_1}{2^{j-1}} + \cdots \frac{a_{j-1}}{2} + a_j + 2a_{j+1} + \cdots + 2^{\ell-j} a_{\ell}.$$ Note that $$S_j:= \frac{a_0}{2^j} + \frac{a_1}{2^{j-1}} + \cdots \frac{a_{j-1}}{2} \le \frac{1}{2^j} + \frac{1}{2^{j-1}} + \cdots + \frac{1}{2} = 1 - \frac{1}{2^j}$$ Furthermore, if $a_{j-1} = 0$, then in fact $S_j < 1/2$.

Set $A_j := \frac{n}{2^j} + \frac{1}{2}$. The inequality above implies that the integer part of $A_j$ is $A_j - S_j$ if $a_{j-1} = 0$ and $A_j - S_j + 1$ if $a_{j-1} = 1$, i.e. the integer part of $A_j$ is simply $A_j - S_j + a_{j-1}$.

Thus, we have $$\sum_{j=1}^{\infty}\lfloor A_j \rfloor = \sum_{j=1}^{\infty} A_j - S_j + a_{j-1} $$

We now compute this sum: $$\sum_{j=1}^{\infty} A_j - S_j +a_{j-1} = \sum_{j=1}^{\ell+1} a_j + 2a_{j+1} + \cdots + 2^{\ell - j} a_{\ell} + a_{j-1} = a_{\ell} (2^{\ell-1} + 2^{\ell-2} + \cdots + 1) + a_{\ell-1} (2^{\ell-2} + \cdots + 1) + \cdots + a_2 (2+1) +a_1 + \sum_{j=1}^{\ell+1} a_{j-1} = 2^{\ell} a_{\ell} + 2^{\ell-1} a_{\ell-1} + \cdots + 2^2 a_2 + 2a_1 - (a_{\ell} + \cdots + a_1) + \sum_{j=1}^{\ell+1} a_{j-1} = 2^{\ell} a_{\ell} + 2^{\ell-1} a_{\ell-1} + \cdots + 2^2 a_2 + 2a_1 + a_0 = n.$$

Answer 2

Let's consider this problem in binary:

Suppose, when written in binary form: $$n=\overline{a_ma_{m-1}\cdots a_1}$$So that $n$ has m digits in binary, and each $a_i$ is either $1$ or $0$, $a_m \neq 0$.

In binary, dividing by 2 is like dividing by 10 in decimal, and adding $\frac{1}{2}$ is the same as adding $0.1$. Hence, for $k=1, 2, ..., m$, $\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor$ contributes to the summation.

Furthermore, for each $k=1, 2, ..., m$, $$\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor=\begin{cases}\frac{n}{2^k} & \mbox{if} \ a_k=0\\ \frac{n}{2^k}+1 & \mbox{if} \ a_k=1\end{cases} $$ (why?)

So, we can write $$\sum_{k=1}^{\infty}\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor =\sum_{k=1}^{m}\frac{\overline{a_ma_{m-1}\cdots a_1}}{2^k}+|\{i:a_i=1\}|\\ =\overline{a_ma_{m-1}\cdots a_2}+\overline{a_ma_{m-1}\cdots a_3}+\cdots +a_m+|\{i:a_i=1\}|$$ Perhaps you can take it from here?

Answer 3

The terms of $f_n(k)= \displaystyle \left[\frac{n}{2^{k}}+\frac{1}{2}\right]$ are integers by definition, and non-negative ones at that. Therefore you know that if the sum is to converge, there must be some $N$ such that for every $k>N$ we have $f_n(k)=0$.

Can you find this $N$?

Answer 4

Hint, use this well known: $$\left[x+\dfrac{1}{2}\right]=[2x]-[x]$$