11
$\begingroup$

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.

  • 0
    n and$m$in Natural number2011-05-07

9 Answers 9

13

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. :)

7

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.

4

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.

4

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

3

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

1

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}

  • 0
    n and m in N . thank u2011-05-07
0

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} ... ?

  • 0
    [chuckle] I'm not upset. Does your teacher not accept the other answers given?2011-05-11
0

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

0

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.