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.

  • 1
    Can I assume $m$ and $n$ are natural numbers?2011-05-07
  • 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
    Three observations: 1) Your last step is the same algebraic manipulation as my answer. 2) I feel like you haven't finished the induction process. 3) You may or may not know this, but it is generally considered polite to accept answers given on your questions (although you don't have to accept the most highly-voted answer).2011-05-09
  • 0
    I'm so sorry to upset u . my teacher is very strict people and don't accept your answer . don't have malice toward me .2011-05-11
  • 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.