I'm reading Concrete Mathematics and stumbled on this question:
Prove the identity
$$ \sum_{0 \leq k<m}\left(\left\lfloor\frac{m+k}{n}\right\rfloor-\left\lfloor\frac{k}{n}\right\rfloor\right)=\left\lfloor\frac{m^{2}}{n}\right\rfloor-\left\lfloor\frac{\min (m \bmod n,(-m) \bmod n)^{2}}{n}\right\rfloor $$
for all positive integers m and n.
Any help would be much appreciated!
I worked on the case where $m<=1/2n$, both LHS and RHS are 0. But I don't know how to solve other cases.
It could occur that provided solutions from books may add extra confusion. At least, this is my impression regarding the solution (perhaps better call it as hint) to problem 3.37 from the book (the one depicted in the original question). Even the authors of the book Concrete Mathematics 2nd Edition warn against prematurely peeking into solutions (this is stated in the introductory section) to avoid being "locked" into specific way of thinking from the very beginning.
That being said, let us see how may we tackle this problem in a different way. It is beneficial to first perform some exploration about what is going on, and try to decipher pertinent properties of the components from the problem. We can identify three major components:
The floor function $\lfloor x \rfloor$ with a real argument x. It is a non-decreasing function with the following properties:
$\forall x, y\in R: (y > x \land \lfloor x \rfloor=\lfloor y \rfloor) \Rightarrow \forall z \in (x, y): \lfloor z \rfloor = \lfloor x \rfloor$.
$\lfloor n+x \rfloor=n+\lfloor x \rfloor$, where n is an integer.
The function $g(m,n)=min(m \bmod n, (-m) \bmod n)$. It maps pairs of integers m and n into a closed interval $\left[0,\frac{n}{2}\right]$. We will use this fact for structuring the argument m, as this will allow a nice cancellation to happen on the right hand side (RHS).
The summation on the left hand side (LHS) with summands involving the floor function.
This is the most crucial part of the solution. It is worthwhile to try applying this heuristic, i.e., to think whether breaking down quantities into smaller constituent parts may help express terms in smoother fashion. It turns out, that it is useful to define $m=pn+qr$, where p and r are non-negative integers, $r \in \left[0,\frac{n}{2}\right]$ and $q \in \{-1, 1\}$. Observe that r is taking values from the image of the function g(m,n) (see above).
Suppose than n=200 and we would like to represent m=175 in the previously mentioned format (it is always possible to do this). We would have $m=2\times100-1\times25$, with p=2, q=-1, and r=25. The number 150 could be described both as $m=1\times100+1\times50$ or $m=2\times100-1\times50$. Finally, m=125 would become $m=1\times100+1\times25$.
On the RHS, using our definition of m, we will get: $$\Bigl\lfloor\frac{p^2n^2+2pnqr+(qr)^2}{n}\Bigr\rfloor-\Bigl\lfloor\frac{min(pn+qr \bmod n, (-pn-qr) \bmod n)^2}{n}\Bigr\rfloor=p^2n+2pqr$$
Notice that the remainder in the second term is $min(qr,-qr)^2$, which is exactly the one from the first summand. Just make sure to properly analyze the cases when q=1 and q=-1.
Similarly as we have structured m, let us represent $k=p'n+r'$, where $r' \in [0, n)$.
Here is the sum expanded with our definitions of m and k:
$$\sum_{p'=0}^{p-1} \sum_{r'=0}^{n-1} \left( \Bigl\lfloor\frac{pn+qr+p'n+r'}{n}\Bigr\rfloor-\Bigl\lfloor\frac{p'n+r'}{n}\Bigr\rfloor\right) + \sum_{r'=0}^{qr-1} \left(\Bigl\lfloor\frac{pn+qr+pn+r'}{n}\Bigr\rfloor-\Bigl\lfloor\frac{pn+r'}{n}\Bigr\rfloor\right)$$
Observe that the factors p' vanish from the whole expression. We are left with the following:
$$\sum_{p'=0}^{p-1} \sum_{r'=0}^{n-1} \left(p+\Bigl\lfloor\frac{qr+r'}{n}\Bigr\rfloor\right) + \sum_{r'=0}^{qr-1} \left(p+\Bigl\lfloor\frac{qr+r'}{n}\Bigr\rfloor\right)$$
How many times do we encounter the term p in total? Well, exactly m times, which gives us the first important term $p(pn+qr)$.
Now we just need to count how many times do we encounter "overflows" in the first sum, i.e., when $qr+r'>n$. Observe that the second sum turns out to be zero as $2qr-1<n$. As r' goes from 0 to n-1, once it reaches n-qr we will have this situation. Therefore, for each p' we will have qr extra 1s. This amounts to the additional pqr term.
All in all, our LHS equals to $p(pn+qr)+pqr=p^2n+2pqr$, which is identical to the RHS.
When q=-1 the floor function will emit -1s instead of 1s. Furthermore, these are going to be issued while r' goes from 0 to $\vert qr\vert-1$. The easiest way to handle this case is to "reformat" $m=pn+qr$ into $m=(p-1)n+1 \times(n+qr)$ when defining p' and r'. For example, when n=200 and $m=2\times100-1\times25$ make it $m=1\times100+1\times75$. Here is how the initial LHS looks like in terms of the original p, q, and r:
$$\sum_{p'=0}^{p-2} \sum_{r'=0}^{n-1} \left(\Bigl\lfloor\frac{pn+qr+p'n+r'}{n}\Bigr\rfloor-\Bigl\lfloor\frac{p'n+r'}{n}\Bigr\rfloor\right) + \sum_{r'=0}^{n+qr-1} \left(\Bigl\lfloor\frac{pn+qr+(p-1)n+r'}{n}\Bigr\rfloor-\Bigl\lfloor\frac{(p-1)n+r'}{n}\Bigr\rfloor\right)$$
At the end, you will end up with the same expressions as in case 1.
This might seem like a lot of work, but once you figured out how to express m all the rest happens rather mechanically (you just need to watch out for trivial mistakes). At any rate, as the LSH is always equal to the RHS we have established the requested proof.
