How to prove $\left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor$?

If we do a little algebra on the right-hand side, we get:

$$\left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n-1}{m} \right\rfloor + 1$$

Hopefully things should be clear from that point on. :)


A vivid conceptual proof: $\:$ If $\rm\:[a,b]\:$ contains a unique integer $\rm\:k\:$ then clearly $\rm\ \lceil a\rceil\: =\: k\: =\: \lfloor b\rfloor\:.$

This applies to $\rm\:\ a = n/m,\:\ b = (n+m-1)/m\:.\:$ Notice that $\rm\:[a,b]\:$ contains a unique integer since $\rm\:m\:$ divides exactly one of the consecutive $\rm\:m\:$ integers $\rm\:n,\:n+1,\:\cdots,\:n+m-1\:.$

Note $\ $ This problem is exercise 3.12 in Graham; Knuth; Patashnik: Concrete Mathematics. Curiously they overlook this simple solution, instead giving essentially the solution in my other answer here.


HINT

We can always write $n = mk - r$ where $0 \leq r < m$ and hence $$\left \lceil \frac{n}{m} \right \rceil = k.$$ Try to argue from this what $\left \lfloor \frac{n+m-1}{m} \right \rfloor$ is.