TAOCP 1.2.4 Exercise 44

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 44. [M24] Show that

$$\sum_{k\ge0}\sum_{1 \le j < b} \left\lfloor \frac{n+j b^k}{b^{k+1}} \right\rfloor = n,$$

if $b$ and $n$ are integers, $n \ge 0$, and $b \ge 2$. What is the value of this sum when $n<0$?

Verified: yes
Solve time: 1m33s

---

Solution

Let

$$ S(n)=\sum_{k\ge0}\sum_{1\le j<b}\left\lfloor \frac{n+j b^k}{b^{k+1}}\right\rfloor . $$

Since $b\ge2$, for fixed $n$ the terms vanish when $b^k>|n|$; hence only finitely many terms are nonzero, and the sum is well defined.

First assume $n\ge0$. Write

$$ n=\sum_{r\ge0} a_r b^r, \qquad 0\le a_r<b, $$

where only finitely many digits $a_r$ are nonzero.

For fixed $k$, write

$$ n=q,b^{k+1}+r, \qquad 0\le r<b^{k+1}. $$

Then

$$ \left\lfloor \frac{n+j b^k}{b^{k+1}}\right\rfloor = q+\left\lfloor \frac{r+j b^k}{b^{k+1}}\right\rfloor . $$

Since $0\le r<b^{k+1}$ and $1\le j<b$,

$$ 0\le r+j b^k <2b^{k+1}, $$

hence the second floor is either $0$ or $1$. It equals $1$ exactly when

$$ r+j b^k\ge b^{k+1}. $$

Write

$$ r=a_k b^k+t, \qquad 0\le t<b^k. $$

Then

$$ r+j b^k=(a_k+j)b^k+t. $$

Because $0\le t<b^k$,

$$ r+j b^k\ge b^{k+1} $$

holds exactly when

$$ a_k+j\ge b. $$

Among the integers $j=1,2,\ldots,b-1$, this occurs for

$$ j=b-a_k,\ b-a_k+1,\ \ldots,\ b-1, $$

which are precisely $a_k$ values of $j$. Therefore

$$ \sum_{1\le j<b} \left\lfloor \frac{n+j b^k}{b^{k+1}}\right\rfloor =(b-1)q+a_k. $$

Summing over $k$,

$$ S(n) = (b-1)\sum_{k\ge0}\left\lfloor\frac{n}{b^{k+1}}\right\rfloor +\sum_{k\ge0} a_k. \tag{1} $$

The second sum is the sum of the base-$b$ digits of $n$. Let

$$ A=\sum_{k\ge0} a_k. $$

Since

$$ n=\sum_{r\ge0} a_r b^r, $$

and

$$ \left\lfloor \frac{n}{b^{k+1}}\right\rfloor = \sum_{r\ge k+1} a_r b^{,r-k-1}, $$

we obtain

$$ \sum_{k\ge0}\left\lfloor \frac{n}{b^{k+1}}\right\rfloor = \sum_{r\ge1} a_r\sum_{k=0}^{r-1} b^{,r-k-1} = \sum_{r\ge1} a_r\frac{b^r-1}{b-1}. $$

Multiplying by $b-1$,

$$ (b-1)\sum_{k\ge0}\left\lfloor \frac{n}{b^{k+1}}\right\rfloor = \sum_{r\ge1} a_r(b^r-1) = n-A. $$

Substituting into (1),

$$ S(n)=(n-A)+A=n. $$

Hence, for every integer $n\ge0$,

$$ \boxed{\sum_{k\ge0}\sum_{1\le j<b} \left\lfloor \frac{n+j b^k}{b^{k+1}}\right\rfloor=n.} $$

Now let $n<0$. Put $m=-n>0$. For fixed $k$, write

$$ m=q,b^{k+1}+r, \qquad 0\le r<b^{k+1}. $$

Then

$$ \left\lfloor\frac{-m+j b^k}{b^{k+1}}\right\rfloor = -q+\left\lfloor\frac{j b^k-r}{b^{k+1}}\right\rfloor . $$

Since

$$ -b^{k+1}<j b^k-r<b^{k+1}, $$

the second floor is $0$ or $-1$. It equals $0$ exactly when

$$ j b^k\ge r. $$

Writing $r=a_k b^k+t$ with $0\le t<b^k$, the inequality becomes

$$ j>a_k, $$

or $j=a_k$ when $t=0$.

Therefore the number of $j\in{1,\ldots,b-1}$ for which the floor equals $0$ is

$$ \begin{cases} b-1-a_k, & t>0,\[2mm] b-a_k, & t=0,\ a_k>0,\[2mm] b-1, & t=0,\ a_k=0. \end{cases} $$

In every case,

$$ \sum_{1\le j<b} \left\lfloor\frac{-m+j b^k}{b^{k+1}}\right\rfloor = -(b-1)q-a_k+\varepsilon_k, $$

where $\varepsilon_k=1$ exactly when $r=0$, that is, when $b^{k+1}\mid m$, and $\varepsilon_k=0$ otherwise.

Hence

$$ S(-m) = -(b-1)\sum_{k\ge0}\left\lfloor\frac{m}{b^{k+1}}\right\rfloor -\sum_{k\ge0}a_k +\sum_{k\ge0}\varepsilon_k. $$

The argument above for positive integers gives

$$ (b-1)\sum_{k\ge0}\left\lfloor\frac{m}{b^{k+1}}\right\rfloor +\sum_{k\ge0}a_k =m. $$

Therefore

$$ S(-m)=-m+\sum_{k\ge0}\varepsilon_k. $$

Let $v_b(m)$ be the largest integer $t\ge0$ such that $b^t\mid m$. Then

$$ \varepsilon_k= \begin{cases} 1,& k+1\le t,\ 0,& k+1>t, \end{cases} $$

so

$$ \sum_{k\ge0}\varepsilon_k=t=v_b(m). $$

Consequently

$$ S(-m)=-m+v_b(m). $$

Since $m=-n$,

$$ \boxed{ \sum_{k\ge0}\sum_{1\le j<b} \left\lfloor \frac{n+j b^k}{b^{k+1}}\right\rfloor = n+v_b(-n), \qquad n<0. } $$

Thus the value of the sum is

$$ \boxed{ \begin{cases} n, & n\ge0,\[2mm] n+v_b(-n), & n<0. \end{cases} } $$