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$ Commented 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$ Commented Nov 30, 2014 at 9:32
  • $\begingroup$ I don't see it anywhere in the statement to prove. $\endgroup$ Commented Nov 30, 2014 at 9:33
  • $\begingroup$ I guess I should put it in my proof part. edited. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .