# Prove that $\left\lceil \frac{n}{m} \right\rceil =\left \lfloor \frac{n+m-1}{m} \right\rfloor$

On a discrete mathematics past paper, I must prove that

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

for all integers $n$ and all positive integers $m$.

I have started a proof by induction thus:

Let $P(m,n)$ be the statement that

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

for all integers $n$ and all positive integers $m$.
Then, according to the technique described here, I must prove the following:

1. Base case: I have already proved that $P(a,b)$, where $a=1$ and where $b$ is the smallest value where $n$ is valid. (Note that this is equivalent to proving that $\lceil n \rceil = \lfloor n \rfloor \space \forall\space n\in\mathbb{Z}.$)
2. Induction over $m$: I must show that $P(k,b) \implies P(k+1,b)$ for some positive integer $k$. THIS IS THE STAGE AT WHICH I AM STUCK.
3. Induction over $n$: I must show that $P(h,k) \implies P(h,k+1)$ for some positive integer $m$ and for some integer $k$ (I think that I must account for the fact that $k$ could be negative OR non-negative).

I will explain why I am stuck.
My inductive hypothesis is that $P(k,b)$ - that is, $\left\lceil \frac{b}{k}\right\rceil = \left\lfloor \frac{b+k-1}{k}\right\rfloor$.
I want to show that this implies $P(k+1,b)$. I have tried to do this by attempting to express $\lceil \frac{b}{k+1} \rceil$ in terms of $\left\lceil \frac{b}{k} \right\rceil$, but have not succeeded.

Any hints would be appreciated.

There exist integers $N,a$ such that $$\frac{n}{m}=N+\frac{a}{m}\ \ \ \text{and}\ \ \ 1\le a\le m.$$

Then, the LHS equals $$\left\lceil\frac nm\right\rceil=N+1.$$ And the RHS equals \begin{align}\left\lfloor\frac{n+m-1}{m}\right\rfloor&=\left\lfloor\frac nm+1-\frac 1m\right\rfloor\\&=\left\lfloor N+1+\frac{a-1}{m}\right\rfloor\\&=N+1+\left\lfloor\frac{a-1}{m}\right\rfloor\\&=N+1.\end{align}

• What if $m|n$ in your first paragraph??!!
– k1.M
Commented May 14, 2015 at 11:47
• @k1.M: Note that $a$ can be $m$. Commented May 14, 2015 at 11:49
• Yes, right...I missed it for a while...+1
– k1.M
Commented May 14, 2015 at 11:50

Hint:

Let $k$ be the (unique) integer with: $n=km+r$ with $r\in\left\{ 0,1,\dots,m-1\right\}$.

Then $\lceil\frac{n}{m}\rceil=k+\lceil\frac{r}{m}\rceil$ and $\lfloor\frac{n+m-1}{m}\rfloor=k+1+\lfloor\frac{r-1}{m}\rfloor$.

So it remains to be shown that $\lceil\frac{r}{m}\rceil=1+\lfloor\frac{r-1}{m}\rfloor$ for $r\in\left\{ 0,1,\dots,m-1\right\}$.

Discern the cases $r=0$ and $r\in\left\{ 1,\dots,m-1\right\}$.

Quick approach: We have, by the division algorithm, that:

$$n=mq+r; \, q,r\in\mathbb Z; \, 0\leq r<m$$

Show that $$\left\lceil \frac{n}{m}\right\rceil = \begin{cases}q&\text{if r=0}\\ q+1&\text{if r\neq 0}\end{cases}$$

Now, if $m>r>0$ then $m>r\geq 1$ so $2m-1>r+m-1\geq m$ and deduce that $$q+1\leq\frac{n+m-1}{m}<q+2$$

• Sorry I'm getting confused how you made the last deduction. I'm trying to manipulate the inequalities but I'm just not able to get the final deduction here. Commented May 16 at 1:32

We have $$\lfloor \frac{n+m-1}{m}\rfloor=\lfloor \frac{n-1}m \rfloor+1$$ Now you have two cases $m|n$ or not...

If $m|n$, then $\lceil \frac nm\rceil=\frac nm$ and $\lfloor\frac{n-1}m\rfloor=\frac nm-1$
Now if $m$ does not devide $n$, then $\lceil \frac nm\rceil=\lfloor\frac nm\rfloor+1$ and $\lfloor\frac nm\rfloor=\lfloor\frac{n-1}m\rfloor$.