How to prove $\left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor$? everybody, how can I prove that, for natural $m$ and $n$,
$$
\left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor \; ?
$$
Thanks a lot.
 A: 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.
A: 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.
A: By the division algorithm $\rm\ n\: =\: k\ m + r,\ \ 0\le r < m\:.\:$ Substituting, the sought identity becomes
$$\rm \left\lceil{\ k\: +\: \frac{r}m}\ \right\rceil\ =\ \left\lfloor{\ k\: +\: \frac{r+m-1}m\ }\right\rfloor$$
This is true since both sides are equal to $\rm\:k\:$ if $\rm\:r = 0\:,\:$ else equal to $\rm\:k+1\ $ if $\rm\ 1 \le r \le m-1\:$
A: $(n+m-1)/m=n/m+1-1/m$. can $1-1/m$ be $\geq(m-n)/m=1-n/m$?
\begin{aligned}
\frac{n+m-1}{m}=\frac{n}{m}+1-\frac{1}{m}
\ \ can \ prove : \  1-\frac{1}{m}\geq \frac{m-n}{m}=1-\frac{n}{m}
\end{aligned}
A: 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: The claim is false for real $n$ and $m$. Take $n = \pi$ and $m = -3$ for a counter-example. It isn't even true for integral $n$ and $m$. Take $n = 3$ and $m = -3$ for a counter-example.
Suppose $n$ and $m$ are positive integers. Let $\chi_{\pm,X}(x)$ denote the characteristic function of $X_{\pm}$ defined to be $1$ if $x \in X_{\pm}$ and $0$ otherwise. Write 
\begin{align}
\lceil \tfrac{n}{m} \rceil = \tfrac{n}{m} - \lbrace \tfrac{n}{m} \rbrace + \chi_{+, \mathbb{R} \setminus \mathbb{Z}}(\tfrac{n}{m}) 
\end{align}
and, similarly,
\begin{align}
\lfloor \tfrac{n + m - 1}{m} \rfloor = \tfrac{n}{m} + 1 - \tfrac{1}{m} - \lbrace \tfrac{n-1}{m} \rbrace
\end{align}
by the $1$-periodicity of the fractional part function. If the claim is to be true, then it must be that 
\begin{align}
\lbrace \tfrac{n}{m} \rbrace - \lbrace \tfrac{n - 1}{m} \rbrace =   \tfrac{1}{m} + \chi_{+, \mathbb{R} \setminus \mathbb{Z}}(\tfrac{n}{m}) - 1.
\end{align}
which is indeed an identity. The extra factors handle the case when $m$ divides $n$, in which case
\begin{align}
\lbrace \tfrac{n}{m} \rbrace - \lbrace \tfrac{n - 1}{m} \rbrace =  \tfrac{1}{m} + 0 - 1.
\end{align}
A: what about Mathematical induction prove :
n and m is natural number :
\begin{aligned} m=1 \rightarrow \left \lfloor \frac{1+n-1}{1} \right \rfloor = \left \lceil \frac{n}{1} \right \rceil \rightarrow true \end{aligned}
\begin{aligned}m=2 \rightarrow \left \lfloor \frac{2+n-1}{2} \right \rfloor = \left \lceil \frac{n}{2} \right \rceil \rightarrow true \end{aligned}
\begin{aligned} \left \lceil \frac{n}{2} \right \rceil = \begin{Bmatrix}
\frac{n}{2} \ n \ is \ even 
\ \
\frac{n+1}{2} \ n \ is \ odd
\end{Bmatrix}
\end{aligned}
\begin{aligned}
if \ m=k \rightarrow \left \lfloor \frac{k+n-1}{k} \right \rfloor = \left \lceil \frac{n}{k} \right \rceil 
\end{aligned}
\begin{aligned}
prove  \ m=k+1 \rightarrow \left \lfloor \frac{k+1+n-1}{k+1} \right \rfloor = \left \lceil \frac{n}{k+1} \right \rceil
\end{aligned}
\begin{aligned} 
\left \lfloor \frac{n-1}{k+1}+1 \right \rfloor = \left \lceil \frac{n}{k+1} \right \rceil 
\end{aligned}
\begin{aligned} 
\left \lfloor \frac{n-1}{k+1} \right \rfloor+1 = \left \lceil \frac{n}{k+1} \right \rceil 
\end{aligned}
... ? 
A: This is basically Bill's solution, I remembered a pretty nice way of writing it:
Let 
$f : {\mathbb Z}_+ \rightarrow {\mathbb R}$ defined by
$$f(x)= \left \lceil \frac{x}{m} \right \rceil - \left \lfloor \frac{x+m-1}{m} \right \rfloor \,.$$
Then 
$$f(x+m)= \left \lceil \frac{x+m}{m} \right \rceil - \left \lfloor \frac{x+2m-1}{m} \right\rfloor =\left \lceil \frac{x}{m} \right \rceil +1- \left \lfloor \frac{x+m-1}{m}\right\rfloor -1=  f(x) $$
Thus, $f$ is periodic of period $m$. 
Moreover $f(0)=0$ and for all $1 \leq x \leq m-1 \,;\, f(x)=1-1=0$.
Since $f$ is periodic and identically zero on a period, $f$ is the zero function.
Last but not least, it is easy to see that if we replace $x \in {\mathbb Z}$ by $x$ positive real, the only step which fails is that $f(x) \neq 0$ for $x \in (0,1)$.
So unless I made a mistake the equality holds on $[0, \infty) \backslash [(0,1)+ {\mathbb Z}]$.
A: Alternatively, we can prove this using $$
(0) \;\;\; p = q \;\equiv\; \langle \forall k :: k \leq p \equiv k \leq q \rangle
$$ which I learned from Bill's answer to another floor question.
Starting at the most complex side of the equality, we calculate for all $\;k\;$:
\begin{align}
& k \le \left \lfloor \frac{n+m-1}{m} \right \rfloor \\
\equiv & \qquad \text{"basic property of floor, allowed since $\;k\;$ is integer"} \\
& k \le \frac{n+m-1}{m} \\
\equiv & \qquad \text{"arithmetic -- to get closer to the shape of the LHS of our equality"} \\
& k \le \frac{n}{m} - \frac{1}{m} + 1 \\
\equiv & \qquad \text{"we may add $\;\frac{1}{m}\;$ if we change $\;\le\;$ to $\;\lt\;$: $\;k\;$ is integer and  $\;0 < \frac{1}{m}< 1\;$"} \\
& k \lt \frac{n}{m} + 1 \\
\equiv & \qquad \text{"basic property of ceiling, allowed since $\;k\;$ is integer"} \\
& k \le \left \lceil \frac{n}{m} \right \rceil \\
\end{align}
By $(0)$ this proves the equality.
