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.

$\endgroup$
  • 1
    $\begingroup$ Can I assume $m$ and $n$ are natural numbers? $\endgroup$ – Fabian May 7 '11 at 5:08
  • $\begingroup$ n and m in Natural number $\endgroup$ – Mobin Shaterian May 7 '11 at 16:33
13
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ n and m in N . thank u $\endgroup$ – Mobin Shaterian May 7 '11 at 16:32
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – El'endia Starman May 9 '11 at 21:09
  • $\begingroup$ 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 . $\endgroup$ – Mobin Shaterian May 11 '11 at 16:17
  • $\begingroup$ [chuckle] I'm not upset. Does your teacher not accept the other answers given? $\endgroup$ – El'endia Starman May 11 '11 at 16:31
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\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.