Concrete Mathematics Section 3.5: Floor / Ceiling sum manipulation

Question

Problem: To find the closed form of $\sum_{0 \le k \lt n}\lfloor \sqrt{k} \rfloor$

The text goes on solving as follows $$ \begin{align} \sum_{0 \le k \lt n}\lfloor \sqrt{k} \rfloor &= \sum_{k,m \ge 0}m[k < n][m = \lfloor \sqrt{k} \rfloor]\\ &= \sum_{k,m \ge 0}m[k < n][m \le \sqrt{k} < m + 1]\\ &= \sum_{k,m \ge 0}m[k < n][m^2 \le k < (m + 1)^2]\\ &= \sum_{k,m \ge 0}m[m^2 \le k < (m + 1)^2 \le n] + \sum_{k,m \ge 0}m[m^2 \le k < n < (m + 1)^2] \end{align} $$

Let's assume that $n = a^2$ is a perfect square. Then the second sum is zsero and the first can be evaluated as

$$ \newcommand{\fallingfactorial}[1]{% ^{\underline{#1}}% } \begin{align} \sum_{k,m \ge 0}m[m^2 \le k < (m + 1)^2 \le a^2] &= \sum_{m \ge 0}m((m + 1)^2 - m^2)[m + 1 \le a]\\ &= \sum_{m \ge 0}m(2m + 1)[m < a]\\ &= \sum_{m \ge 0}(2m\fallingfactorial{2} + 3m\fallingfactorial{1})[m < a]\\ &= \sum_0^a (2m\fallingfactorial{2} + 3m\fallingfactorial{1}) \delta m\\ &= \frac{1}{6}(4a + 1)a(a - 1) \end{align} $$

The next part I don't understand

It says: In general we can let a = $\lfloor \sqrt{n} \rfloor$; then we merely need to add the term $a^2 \le k < n$, which are all equal to a, so they sum to $(n - a^2)a$. This gives the desired closed form,

$$ \sum_{0 \le k < n} \lfloor \sqrt{k} \rfloor = na - \frac{1}{3}a^3 - \frac{1}{2}a^2 - \frac{1}{6}a, \text{where } a = \lfloor \sqrt{n} \rfloor $$

Why we are considering $a^2 \le k \lt n$, shouldn't we consider $a \le k \lt n$ as we have already calculated for $0 \le k \lt a$ before ?

Answer 1

We consider the second sum in somewhat more detail which might help to clarify the situation.

We obtain \begin{align*} \color{blue}{\sum_{k,m\geq 0}}&\color{blue}{m[m^2\leq k<n<(m+1)^2]}\tag{1}\\ &=\sum_{k\geq 0}a[a^2\leq k<n<(a+1)^2]\tag{2}\\ &=\sum_{{k\geq 0}\atop{a^2\leq k <n}}a\tag{3}\\ &=\sum_{a^2\leq k <n}a=\sum_{k=a^2}^{n-1}a\tag{4}\\ &\color{blue}{=(n-a^2)a} \end{align*}

Comment:

• In (1) we observe that if $n$ is fixed there is precisely one integer $m$ which fulfills the condition $$[m^2\leq k<n<(m+1)^2]$$ So, we sum in fact only over $k$.

• In (2) we sum over $k$ only and denote the single value $m$ with $a$. We have $$m=a=\lfloor \sqrt n\rfloor$$ The condition $[\color{blue}{a^2\leq k<n}<(a+1)^2]$ tells us that we have a non-zero contribution only if $a^2\leq k<n$.

• In (3) we rewrite the condition from (2) as index range.

• In (4) we do a small simplification.