Is there any relation between $\lfloor n/k\rfloor$ and $\lfloor n/(k+1)\rfloor$?

Question

Given two integers $n$ and $k$ such that $n\geq k+1$.

Can we find any relation between $\left\lfloor\dfrac{n}{k}\right\rfloor$ and $\left\lfloor \dfrac{n}{k+1}\right\rfloor$?

At first, I thought that $\left\lfloor \dfrac{n}{k+1}\right\rfloor=\left\lfloor\dfrac{n}{k}\right\rfloor-1,$ but then I found that, for $k=1$, $$\left\lfloor\dfrac{n}{2}\right\rfloor\neq n-1$$. So, I guess that $$\left\lfloor \dfrac{n}{k+1}\right\rfloor\leq\left\lfloor\dfrac{n}{k}\right\rfloor-1.$$ How can we prove this? Is this the best bound?

Answer 1

The floor function satisfies

• $\lfloor x\rfloor\leq x$
• $\lfloor\lfloor x\rfloor\rfloor=\lfloor x\rfloor$
• From those two one can easily prove that $$ \lfloor x\rfloor +\lfloor y\rfloor\leq \lfloor x+y\rfloor $$
• If we subtract $\lfloor y\rfloor$ from both sides and consider $x=a$ and $y=b-a$ we then get $$ \lfloor a\rfloor \leq \lfloor b\rfloor-\lfloor b-a\rfloor $$

To apply the last rule to your question, we must consider the difference between the two fractions inside the floor functions you are asking about: $$ \begin{align} a &= \frac n{k+1}\\ b &= \frac nk\\ b-a &= \frac nk-\frac n{k+1}\\ &=\frac n{k(k+1)} \end{align} $$ so applying the rule $\lfloor a\rfloor \leq \lfloor b\rfloor-\lfloor b-a\rfloor$ this gets us $$ \left\lfloor\frac n{k+1}\right\rfloor\leq \left\lfloor\frac n{k}\right\rfloor-m $$ where $$ m=\left\lfloor\frac n{k(k+1)}\right\rfloor $$ depends entirely on the size of $n$ relative to $k(k+1)$. If $n<k(k+1)$ we even have $m=0$ so the only constant you may subtract is in fact just zero, not $1$. So unfortunately we only have the very unsurprising $$ \left\lfloor\frac n{k+1}\right\rfloor\leq \left\lfloor\frac n{k}\right\rfloor $$ which appears to be not helpful at all.

Answer 2

First let's consider that $$ \eqalign{ & \left\lfloor {x + y} \right\rfloor = \cr & = \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left\lfloor {\left\{ x \right\} + \left\{ y \right\}} \right\rfloor = \cr & = \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left[ {1 - \left\{ x \right\} \le \left\{ y \right\}} \right] \cr} $$ where the curly brackets denotes the fractional part and where in the last line $[P]$ denotes the Iverson bracket.

Then we have $$ \eqalign{ & \left\lfloor {{n \over k}} \right\rfloor = \left\lfloor {{n \over {k + 1}}{{k + 1} \over k}} \right\rfloor = \left\lfloor {{n \over {k + 1}} + {n \over {k\left( {k + 1} \right)}}} \right\rfloor = \cr & = \left\lfloor {{n \over {k + 1}}} \right\rfloor + \left\lfloor {{n \over {k\left( {k + 1} \right)}}} \right\rfloor + \left[ {1 - \left\{ {{n \over {k + 1}}} \right\} \le \left\{ {{n \over {k\left( {k + 1} \right)}}} \right\}} \right] \cr} $$ which tells much about the difference between the two floors.