1
$\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$
1
$\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$
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$
  • $\begingroup$ What if $m|n$ in your first paragraph??!! $\endgroup$ – k1.M May 14 '15 at 11:47
  • $\begingroup$ @k1.M: Note that $a$ can be $m$. $\endgroup$ – mathlove May 14 '15 at 11:49
  • 1
    $\begingroup$ Yes, right...I missed it for a while...+1 $\endgroup$ – k1.M May 14 '15 at 11:50
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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.