3
$\begingroup$

Suppose x,y $ \in \mathbb{Z}^+ $

Prove $\lceil x/y \rceil = \lfloor (x-1)/y \rfloor + 1$

I was considering using the definition of floor and ceiling to prove this. But this does not seem like a valid proof to me as I assume the right hand side is already equal to the left hand side.

This is what I have so far:

Let n$ \in \mathbb{Z} $

$\lceil x/y \rceil = n \iff n-1 < x/y \leq n $

$\lfloor (x-1)/y \rfloor = n -1 \iff n-1 \leq (x-1)/y < n $
Then $\lfloor (x-1)/y \rfloor +1 = n \iff n-1 \leq (x-1)/y < n + 1 $

Then both sides are equivalent.

Would a better way be to prove using a contradiction by assuming both sides are not equal?

$\endgroup$
4
  • $\begingroup$ What does $n$ have to do with all this? $\endgroup$ Nov 30, 2014 at 9:31
  • $\begingroup$ n is the result of the floor and ceiling function. eg. $ \lceil 5/2\rceil = 3 $ So n = 3. $\endgroup$ Nov 30, 2014 at 9:32
  • $\begingroup$ I don't see it anywhere in the statement to prove. $\endgroup$ Nov 30, 2014 at 9:33
  • $\begingroup$ I guess I should put it in my proof part. edited. $\endgroup$ Nov 30, 2014 at 9:34

3 Answers 3

3
$\begingroup$

If $y$ divides $x$ then:

  • $\lceil\frac{x}{y}\rceil=\frac{x}{y}$
  • $\lfloor\frac{x-1}{y}\rfloor=\frac{x}{y}-1$

Hence $\lceil\frac{x}{y}\rceil=\lfloor\frac{x-1}{y}\rfloor+1$


If $y$ does not divide $x$ then:

  • $\lceil\frac{x}{y}\rceil=\lfloor\frac{x}{y}\rfloor+1$
  • $\lfloor\frac{x-1}{y}\rfloor=\lfloor\frac{x}{y}\rfloor$

Hence $\lceil\frac{x}{y}\rceil=\lfloor\frac{x-1}{y}\rfloor+1$

$\endgroup$
2
  • $\begingroup$ I'm confused as to how you obtained the y does not x case. Did you use the definition of floor and ceiling? Also, wouldn't any positive integer divide another positive integer? $\endgroup$ Nov 30, 2014 at 9:50
  • $\begingroup$ @onesevenfour: 1. There are two statements there, which one are you confused about? 2. When I say "divide", I mean "divide without a remainder" (what else could it mean? the only number that does not divide other numbers is $0$). $\endgroup$ Nov 30, 2014 at 9:52
1
$\begingroup$

starting from line 2, the inequality can be rewritten as

\begin{equation*} n-1+1/y \leq x/y < n+1/y \end{equation*} since x,y are integers, the left inequality is equivalent to

\begin{equation*} n-1 < x/y \end{equation*}

and the right inequality is equivalent to \begin{equation*} x/y \leq n \end{equation*}

$\endgroup$
2
  • $\begingroup$ I get this proof, but does the case $\lfloor (x-1)/y \rfloor \neq n -1$ need to be considered? $\endgroup$ Nov 30, 2014 at 9:54
  • $\begingroup$ I edited it to be more clear. this shows that the right hand sides of the first two lines are equivalent. therefore the left hand sides are as well $\endgroup$
    – Dunham
    Nov 30, 2014 at 10:14
1
$\begingroup$

I might want to use a property of integer arithmetic $a \lt b \iff a+1 \le b$, as in:

$\qquad\;\;\lceil x/y \rceil = n $

$ \iff n-1 \lt x/y \leq n $

$ \iff (n-1)y \lt x \leq ny $

$\iff (n-1)y \le x-1 \lt ny$

$\iff n-1 \le (x-1)/y \lt n $

$\iff \lfloor(x-1)/y\rfloor =n-1$

$\iff \lfloor(x-1)/y\rfloor +1=n$

so $\lceil x/y \rceil = \lfloor(x-1)/y\rfloor$ + 1

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