Problem: Calculate the following sum: $$ S = \sum_{k=1}^{9999} \lfloor \sqrt{k} \rfloor $$

While computing this term by term is trivial for a computer, finding a general closed formula offers a nice exercise in summation manipulation and integer properties. Let's derive the general solution for any $n$ and then apply it to our specific case.

The General Approach

Let $n, m \in \mathbb{N}$ such that $m$ is the integer part of the square root of $n$, that is, $m^2 \le n < (m+1)^2$.

The key idea is to group the terms based on the values of $\lfloor \sqrt{k} \rfloor$. We can split the total summation into three distinct parts:

1. The intervals strictly between consecutive squares.
2. The "tail" from $m^2 + 1$ to $n$.
3. The perfect squares themselves (where the floor function is exact).

We can rewrite the sum as:

$$ \sum_{k=1}^{n}\lfloor\sqrt{k}\rfloor = \underbrace{\sum_{j=2}^{m}\sum_{k=(j-1)^{2}+1}^{j^{2}-1}\lfloor\sqrt{k}\rfloor}_{\text{Intervals}} + \underbrace{\sum_{k=m^{2}+1}^{n}\lfloor\sqrt{k}\rfloor}_{\text{Tail}} + \underbrace{\sum_{j=1}^{m}\lfloor\sqrt{j^{2}}\rfloor}_{\text{Perfect Squares}} $$

Analyzing the Terms

1. The Intervals:
For any $k$ in the range $(j-1)^2 + 1 \le k \le j^2 - 1$, we have strict inequalities $(j-1)^2 < k < j^2$. Taking square roots, $j-1 < \sqrt{k} < j$. Therefore, the floor function is constant: $$ \lfloor \sqrt{k} \rfloor = j-1 $$

2. The Tail:
Since $m$ is the largest integer such that $m^2 \le n$, for the range $m^2 + 1 \le k \le n$, we have $\lfloor \sqrt{k} \rfloor = m$.

3. The Perfect Squares:
Simply, $\lfloor \sqrt{j^2} \rfloor = j$.

Substituting these values back into our equation:

$$ \sum_{k=1}^{n}\lfloor\sqrt{k}\rfloor = \sum_{j=2}^{m}\left( (j-1) \sum_{k=(j-1)^{2}+1}^{j^{2}-1} 1 \right) + m\sum_{k=m^{2}+1}^{n} 1 + \sum_{j=1}^{m} j $$

Simplification

Let's count the number of terms in the inner sums.
The number of terms in the interval $((j-1)^2, j^2)$ is: $$ (j^2 - 1) - [(j-1)^2 + 1] + 1 = j^2 - 1 - (j^2 - 2j + 1) = 2j - 2 $$ The number of terms in the tail is simply $n - m^2$.
And the sum of integers is the standard triangular number formula $\frac{m(m+1)}{2}$.

Thus, the expression becomes:

$$ \begin{aligned} S &= \sum_{j=2}^{m} (j-1)(2j-2) + m(n - m^2) + \frac{m(m+1)}{2} \\ &= 2\sum_{j=2}^{m} (j-1)^2 + m(n - m^2) + \frac{m^2 + m}{2} \end{aligned} $$

Using the formula for the sum of the first $k$ squares, $\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$, and shifting the index $j-1 \to i$ (where $i$ goes from 1 to $m-1$):

$$ 2\sum_{i=1}^{m-1} i^2 = 2 \left[ \frac{(m-1)m(2(m-1)+1)}{6} \right] = \frac{m(m-1)(2m-1)}{3} $$

Combining everything, we arrive at the closed formula:

Solution to the Problem

For our specific case, $n = 9999$. Since $99^2 = 9801$ and $100^2 = 10000$, we have $m = 99$.

Substituting into our formula:

$$ \begin{aligned} S &= 99(9999 - 99^2) + \frac{1}{6}(99)(4(99^2) - 3(99) + 5) \\ &= 99(198) + \frac{33}{2}(39204 - 297 + 5) \\ &= 19,602 + \frac{33}{2}(38,912) \\ &= 19,602 + 642,048 \\ &= \mathbf{661,650} \end{aligned} $$