Exercise 4.1.14* (Prove $\sum_{j=1} \left \lfloor \frac{n}{2^j}+ \frac{1}{2} \right \rfloor = n $)

Proof.

(a)

Let $k\in \mathbb{N}$. Consider the sets $$\begin{array}{llll}\hfill A_k& =\{i\in [[1,n]]:2^k\mid i\},& \hfill & \\ \hfill B_k& =\{i\in [[1,n]]:2^k\mid i,2^{k+1}\nmid i\},& \hfill & \end{array}$$

so that $A_k$ is the set of multiples of $2^k$ between $1$ and $n$, and $B_k$ the set of $i$’s between $1$ and $n$ that are divisible by $2^k$ but not $2^{k+1}$. We want to estimate the number of elements of $B_k$, written $|B_k|$.

Note first that $A_{k+1}\subset A_k$ for all $k\in \mathbb{N}$, because $2^{k+1}\mid i$ implies that $2^k\mid i$. Moreover $B_k=A_k\setminus A_{k+1}$ by definition of $B_k$, so

$$\begin{array}{lll}\hfill |B_k|& =|A_k|-|A_{k+1}|& \hfill \text{(1)}\end{array}$$

By Theorem 4.1(10), we obtain

$$|A_k|=\lfloor \frac{n}{2^k}\rfloor ,$$

thus

$$\begin{array}{lll}\hfill |B_k|& =\lfloor \frac{n}{2^k}\rfloor -\lfloor \frac{n}{2^{k+1}}\rfloor .& \hfill \text{(2)}\end{array}$$

The number of $i\in [[1,n]]$ that are divisible by $2^k$ but not $2^{k+1}$ is $\lfloor \frac{n}{2^k}\rfloor -\lfloor \frac{n}{2^{k+1}}\rfloor$.

(b)

By Problem 6, $\lfloor x\rfloor ∕\lfloor x+\frac{1}{2}\rfloor =\lfloor 2x\rfloor$ for any real number $x$. Applying this formula to $x=n∕2^{k+1}$, we obtain $$\lfloor \frac{n}{2^{k+1}}\rfloor +\lfloor \frac{n}{2^{k+1}}+\frac{1}{2}\rfloor =\lfloor \frac{n}{2^k}\rfloor ,$$

thus, by equation (2),

$$\begin{array}{llll}\hfill |B_k|& =\lfloor \frac{n}{2^k}\rfloor -\lfloor \frac{n}{2^{k+1}}\rfloor & \hfill & \\ \hfill & =\lfloor \frac{n}{2^{k+1}}+\frac{1}{2}\rfloor .& \hfill & \end{array}$$

If $i\in [[1,n]]$, then $i\in B_k$ if and only if $k={\nu }_p(i)\in \mathbb{N}$. So

$$[[1,n]]=\underset{k\in \mathbb{N}}{\bigcup }{B}_k,\text{(disjoint union)}.$$

Therefore

$$\begin{array}{llllll}\hfill n& =\underset{k=0}{\overset{\infty }{\sum }}|B_k|& \hfill & & \hfill & \\ \hfill & =\underset{k=0}{\overset{\infty }{\sum }}\lfloor \frac{n}{2^{k+1}}+\frac{1}{2}\rfloor & \hfill & & \hfill & \\ \hfill & =\underset{j=1}{\overset{\infty }{\sum }}\lfloor \frac{n}{2^j}+\frac{1}{2}\rfloor & \hfill (j=k+1),& & \hfill & & \hfill \end{array}$$

so we obtain the desired result

$$\begin{array}{lll}\hfill n=\underset{j=1}{\overset{\infty }{\sum }}\lfloor \frac{n}{2^j}+\frac{1}{2}\rfloor .& & \hfill \text{(3)}\end{array}$$

(c)

By Theorem 4.1(8), $\lfloor \frac{n}{2^{k+1}}+\frac{1}{2}\rfloor$ is the nearest integer of $\frac{n}{2^{k+1}}$, using the larger one if two exist.

Note that

$$n=\underset{j=1}{\overset{\infty }{\sum }}\frac{n}{2^j}.$$

If we replace each term by its nearest integer, we obtain by equation (3) the same result $n$:

$$\begin{array}{lll}\hfill n=\underset{j=1}{\overset{\infty }{\sum }}\frac{n}{2^j}=\underset{j=1}{\overset{\infty }{\sum }}\lfloor \frac{n}{2^j}+\frac{1}{2}\rfloor .& & \hfill \end{array}$$