TAOCP 1.2.4 Exercise 42

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 42. [M24] (a) Prove that

$$\sum_{k=1}^n a_k = na_n - \sum_{k=1}^{n-1} k(a_{k+1}-a_k),\qquad \text{if } n>0.$$

(b) The preceding formula is useful for evaluating certain sums involving the floor function. Prove that, if $b$ is an integer $\ge 2$,

$$ \sum_{k=1}^n \lfloor \log_b k \rfloor = (n+1)\lfloor \log_b n \rfloor - \frac{b^{\lfloor \log_b n \rfloor +1}-b}{b-1}. $$

Verified: no
Solve time: 32s

---

Solution

(a)

We prove the identity

$$ \sum_{k=1}^n a_k = na_n-\sum_{k=1}^{n-1}k(a_{k+1}-a_k), \qquad n>0. $$

Expand the second sum:

$$ \sum_{k=1}^{n-1}k(a_{k+1}-a_k) = \sum_{k=1}^{n-1}ka_{k+1} - \sum_{k=1}^{n-1}ka_k. $$

Reindex the first sum by setting $j=k+1$:

$$ \sum_{k=1}^{n-1}ka_{k+1} = \sum_{j=2}^{n}(j-1)a_j. $$

Hence

$$ \sum_{k=1}^{n-1}k(a_{k+1}-a_k) = \sum_{j=2}^{n}(j-1)a_j - \sum_{k=1}^{n-1}ka_k. $$

Writing both sums with the same index,

$$= (a_2+2a_3+\cdots +(n-1)a_n) - (a_1+2a_2+\cdots +(n-1)a_{n-1}).$$

Combine terms:

$$= -a_1-a_2-\cdots -a_{n-1}+(n-1)a_n.$$

Therefore

$$ na_n-\sum_{k=1}^{n-1}k(a_{k+1}-a_k) = na_n- \bigl(-(a_1+\cdots+a_{n-1})+(n-1)a_n\bigr), $$

which simplifies to

$$= a_1+\cdots+a_{n-1}+a_n = \sum_{k=1}^n a_k.$$

Thus

$$ \boxed{ \sum_{k=1}^n a_k = na_n-\sum_{k=1}^{n-1}k(a_{k+1}-a_k) } $$

for all $n>0$.

This completes the proof.

∎

(b)

Let

$$ a_k=\lfloor \log_b k\rfloor, \qquad b\ge2. $$

By part (a),

$$ \sum_{k=1}^n\lfloor \log_b k\rfloor = n\lfloor \log_b n\rfloor - \sum_{k=1}^{n-1} k\bigl( \lfloor \log_b(k+1)\rfloor - \lfloor \log_b k\rfloor \bigr). \tag{1} $$

Let

$$ m=\lfloor \log_b n\rfloor. $$

Then

$$ b^m\le n<b^{m+1}. $$

The quantity

$$ \lfloor \log_b(k+1)\rfloor - \lfloor \log_b k\rfloor $$

is nonzero precisely when $k+1$ is a power of $b$. Since

$$ \lfloor \log_b(b^j)\rfloor=j, \qquad \lfloor \log_b(b^j-1)\rfloor=j-1, $$

the difference equals $1$ when $k=b^j-1$ and equals $0$ otherwise.

Since $b^m\le n<b^{m+1}$, the values

$$ b^1,b^2,\ldots,b^m $$

are exactly the powers of $b$ not exceeding $n$. Therefore the nonzero terms in (1) occur for

$$ k=b^j-1, \qquad 1\le j\le m, $$

and (1) becomes

$$ \sum_{k=1}^n\lfloor \log_b k\rfloor = nm-\sum_{j=1}^{m}(b^j-1). $$

Evaluate the geometric sum:

$$ \sum_{j=1}^{m}(b^j-1) = \sum_{j=1}^{m}b^j-m = \frac{b^{m+1}-b}{b-1}-m. $$

Hence

$$ \sum_{k=1}^n\lfloor \log_b k\rfloor = nm- \left( \frac{b^{m+1}-b}{b-1}-m \right), $$

so

$$= (n+1)m-\frac{b^{m+1}-b}{b-1}.$$

Substituting $m=\lfloor \log_b n\rfloor$ gives

$$ \boxed{ \sum_{k=1}^n \lfloor \log_b k \rfloor = (n+1)\lfloor \log_b n \rfloor - \frac{ b^{\lfloor \log_b n \rfloor+1}-b }{b-1} }. $$

This completes the proof.

∎