TAOCP 1.2.4 Exercise 43

We wish to evaluate $S_n = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor.$ Let $m = \lfloor \sqrt{n} \rfloor$, so that $m^2 \le n < (m+1)^2$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 43. [M23] Evaluate $\sum_{k=1}^n \lfloor \sqrt{k} \rfloor$.

Verified: yes
Solve time: 2m17s

Solution

We wish to evaluate

$S_n = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor.$

Let $m = \lfloor \sqrt{n} \rfloor$, so that $m^2 \le n < (m+1)^2$. Observe that for any integer $i \ge 0$, the numbers $k$ satisfying

$i^2 \le k < (i+1)^2$

all have

$\lfloor \sqrt{k} \rfloor = i.$

The number of integers $k$ in this range is $(i+1)^2 - i^2 = 2i+1$. Therefore, we can partition the sum $S_n$ according to the value of $\lfloor \sqrt{k} \rfloor$:

S_n = \sum_{i=0}^{m-1} i \cdot (2i+1) + m \cdot (n - m^2 + 1). \tag{1}

Here the term $m \cdot (n - m^2 + 1)$ accounts for the last, possibly incomplete, block of integers from $m^2$ to $n$.

Compute the first sum:

$$ \sum_{i=0}^{m-1} i(2i+1) = \sum_{i=0}^{m-1} (2i^2 + i) = 2 \sum_{i=0}^{m-1} i^2 + \sum_{i=0}^{m-1} i. $$

Using standard formulas for sums of squares and sums of integers:

$$ \sum_{i=0}^{m-1} i = \frac{(m-1)m}{2}, \quad \sum_{i=0}^{m-1} i^2 = \frac{(m-1)m(2m-1)}{6}. $$

Therefore,

$$ 2 \sum_{i=0}^{m-1} i^2 + \sum_{i=0}^{m-1} i = 2 \cdot \frac{(m-1)m(2m-1)}{6} + \frac{(m-1)m}{2} = \frac{(m-1)m(2m-1)}{3} + \frac{(m-1)m}{2}. $$

Combine the two terms over a common denominator $6$:

$$ \frac{2(m-1)m(2m-1)}{6} + \frac{3(m-1)m}{6} = \frac{(m-1)m(4m - 2 + 3)}{6} = \frac{(m-1)m(4m +1)}{6}. $$

Thus the sum (1) becomes

$$ S_n = \frac{(m-1)m(4m +1)}{6} + m (n - m^2 + 1). $$

Substituting $m = \lfloor \sqrt{n} \rfloor$, we have the final formula

$$ \boxed{S_n = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor = \frac{\lfloor \sqrt{n} \rfloor , (\lfloor \sqrt{n} \rfloor - 1)(4 \lfloor \sqrt{n} \rfloor +1)}{6} + \lfloor \sqrt{n} \rfloor , (n - \lfloor \sqrt{n} \rfloor^2 +1)}. $$

This completes the solution. ∎