1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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