4
$\begingroup$

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.

$\endgroup$
0

4 Answers 4

5
$\begingroup$

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}$$

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

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\} $.

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Bob Marley
    Commented May 16 at 1:32
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .