Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Can I assume $m$ and $n$ are natural numbers? –  Fabian May 7 '11 at 5:08
    
n and m in Natural number –  mobin S.S.Bidgoli May 7 '11 at 16:33

9 Answers 9

up vote 11 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
+1: This is very nice. –  Mike Spivey May 9 '11 at 18:36
    
thanks for your book that introduced –  mobin S.S.Bidgoli May 19 '11 at 9:14

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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}

share|improve this answer
    
n and m in N . thank u –  mobin S.S.Bidgoli May 7 '11 at 16:32

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

share|improve this answer
    
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). –  El'endia Starman May 9 '11 at 21:09
    
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 . –  mobin S.S.Bidgoli May 11 '11 at 16:17
    
[chuckle] I'm not upset. Does your teacher not accept the other answers given? –  El'endia Starman May 11 '11 at 16:31

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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