Is ceil(n/k) equal to floor((n-1)/k) + 1 for positive integer values of n and k?

[r0bHadz]

Homework Statement

Alright guys this took me an hour because I am really, really... i don't want to say it. I'm about to pop a gasket if my argument is not logical.

I couldn't find any info on the latex primer on floor and ceil symbols so i apologize in advance

show that if n and k are positive integers, then ceil(n/k) = floor((n-1)/k) + 1

Homework Equations

The Attempt at a Solution

let n/k = x - ε where x is a positive int and 0≤ε<1

ceil(n/k) = ceil(x-ε) = x

from n/k = x - ε, n = k(x-ε) => n-1 = k(x-ε) - 1 => (n-1)/k = (x-ε) - (1/k)

floor((n-1)/k) + 1 = floor( (x)+( -ε - (1/k))) +1

I want to evaluate floor( (x)+( -ε - (1/k)))

since k can only be an int, k=1, it becomes clear that -ε will be zero, as there will be no ε in n/k = x - ε

so floor(x-1) + 1 = x-1 + 1 = x, which = ceil(x-ε). For k = 1, ceil(n/k) = floor((n-1)/k) + 1

floor(n/k) = floor (x-ε) = x-1

floor((n-1) / k) = floor (x-ε-(1/k)) = y

x-1 ≥ y for all values of positive ints n and k, so I don't think I even had to use the case where k=1..

but since its a floor function, y has to be x-1, because besides k=1 where it will be exactly x-1, -∈-(1/k) will always produce a number 0<-∈-(1/k)<1, and due to the floor property, it will always be x-1.

So
ceil(n/k) = floor((n-1)/k) + 1

I hope this makes sense my home dogs

 

[StoneTemplePython]

so your claim is

$\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n-1}{k}}\rfloor +1$

you just completed a proof involving modular arithmetic... wouldn't it be good to practice using modular arithmetic here? My general motto is don't start from scratch and this problem seems taylor made for modular arithmetic.
- - - -
you can write any positive integer $n$ as
$n = r\cdot k + c$
where $r$ is a non-negative integer
and $c := n\%k$

you know how the 'wraparound' with modular arithmetic works -- and since we are talking subtracting 1 from n before dividing by k, it would seem to motivate two cases

one where $c \geq 1$ and one where $c= 0$. The first should be very easy to prove, and I'm confident you can do the second one...

- - - -

Alright guys this took me an hour because I am really, really... i don't want to say it. I'm about to pop a gasket if my argument is not logical.

Don't blow a gasket!

I get the impression that at least some of what you are doing in Rosen's book is self study... if you detest the book, there are several other gentler books to learn proofs from, say in the New Math Library... also MIT Open Courseware has a nice discrete math /intro proofs course online called "Math for CS"...

it can be frustrating to learn proofs or learn a new kind of math... but some of it comes down to how 'good' the book is and especially how good a fit it is for you.

 

[r0bHadz]

I appreciate it. For some reason I just found the proof easier without the mod operator. I went to my teacher and she checked it and said it was fine. However, there are multiple ways to do this proof. It seems induction is viable as well.

The only reason I'm doing every question in Rosen's book is so I can get a complete understanding/ get an A in the course. My school has 2 discrete math courses, I'm taking the second one right now. It's all proof based so its very difficult but whatever. I just want to make sure I'm understanding everything.

I appreciate the help my brotha