# Prove a relationship involving floor functions

I am trying to prove that a particular expression is a lower bound for a very unusually-behaved function. The whole proof will be complete if I can just nail down the details of one technical lemma involving the floor function. I am completely confident that the lemma is true, but have had a devil of a time proving it.

The Lemma is as follows:

Let $n$ and $b$ be natural numbers, with $1 \leq b \leq n$. Suppose that there exists an integer $k$ such that $$\frac{n + \sqrt{n^2 + b + 2}}{b+2} < k < \frac{n+\sqrt{n^2+b+1}}{b+1}$$ Then there exists an integer lying strictly between $$\left( \left\lfloor \frac{n+\sqrt{n^2+b+2}}{b+2} \right\rfloor +1 \right)\sqrt{n^2+b+1}$$ and $$\left( \left\lfloor \frac{n+\sqrt{n^2+b+2}}{b+2} \right\rfloor +1 \right)\sqrt{n^2+b+2}$$ (where $\lfloor x \rfloor$ denotes the floor function).

The hypothesis can easily be restated in the form:

Suppose $\left\lfloor \frac{n+\sqrt{n^2+b+2}}{b+2} \right\rfloor < \left\lfloor \frac{n+\sqrt{n^2+b+1}}{b+1} \right\rfloor$

and it's clear that the two inequalities are closely related, but I have not been able to get from one to the other, and I would appreciate any assistance. If there's interest, I can provide more background to the problem.

Edited to add: In fact, I am now almost certain that the Lemma above is actually if-and-only-if, and would also be happy to have help with the proof of the converse.

• You write: $$\left( \left\lfloor \frac{n+\sqrt{n^2+b+2}}{b+2} \right\rfloor +1 \right)\sqrt{n^2+b+1}$$ Are you sure that should not be: $$\left( \left\lfloor \frac{n+\sqrt{n^2+b+1}}{b+1} \right\rfloor +1 \right)\sqrt{n^2+b+1}$$ Uhm, well, for symmetry reasons .. – Han de Bruijn Apr 19 '15 at 14:05
• Nope, it's what I wrote. – mweiss Apr 19 '15 at 14:25

## 1 Answer

Fix $n,b$ with $1\le b\le n$.

Let $k\in\mathbb Z$. For $i\in\{1,2\}$ define $$\tag1\delta_i:=k- \frac{n+\sqrt{n^2+b+i}}{b+i}.$$ Then $k$ is strictly between the bounds iff $\delta_1<0<\delta_2$. Then for $i\in\{1,2\}$ \begin{align}k\sqrt{n^2+b+i}&=\left( \frac{n+\sqrt{n^2+b+i}}{b+i}+\delta_i\right)\sqrt{n^2+b+i}\\ &=\frac{n^2+b+i+n\sqrt{n^2+b+i}}{b+i}+\delta_i\sqrt{n^2+b+i}\\ &=1+n\cdot \frac{n+\sqrt{n^2+b+i}}{b+i}+\delta_i\sqrt{n^2+b+i}\\ &\tag2=1+nk+\delta_i(\sqrt{n^2+b+i}-n).\end{align} Note that $$n<\sqrt{n^2+b+i}\le\sqrt{n^2+n+2}\le\sqrt{n^2+2n+1}=n+1$$ so that $$\tag30<\sqrt{n^2+b+i}-n\le 1$$ with equality on the right if and only if $n=b=1$ and $i=2$. In other words, we have $$\tag{4}0<\sqrt{n^2+b+i}-n< 1\rlap{\qquad\text{if n>1}.}$$

Lemma. Let $k\in\mathbb Z$. Then $k$ is strictly between $\frac{n+\sqrt{n^2+b+2}}{b+2}$ and $\frac{n+\sqrt{n^2+b+1}}{b+1}$ if and only if $1+nk$ is strictly between $k\sqrt{n^2+b+1}$ and $k\sqrt{n^2+b+2}$.

Proof. Because of $(3)$ and $(2)$, the conclusion holds if and only if $\delta_1<0<\delta_2$. But that is equivalent to the premise. $_\square$

Proposition. Let $k=\left\lfloor\frac{n+\sqrt{n^2+b+2}}{b+2}+1\right\rfloor$. There exists an integer strictly between $\frac{n+\sqrt{n^2+b+2}}{b+2}$ and $\frac{n+\sqrt{n^2+b+1}}{b+1}$ if and only if there exists an integer strictly between $k\sqrt{n^2+b+1}$ and $k\sqrt{n^2+b+2}$.

Proof. Assume there exists an integer strictly between $\frac{n+\sqrt{n^2+b+2}}{b+2}$ and $\frac{n+\sqrt{n^2+b+1}}{b+1}$. Then $k$ is certainly such an integer because it is the smallest integer strictly larger than $\frac{n+\sqrt{n^2+b+2}}{b+2}$. Then by the lemma, $1+nk$ is strictly between $k\sqrt{n^2+b+1}$ and $k\sqrt{n^2+b+2}$.

Conversely assume that $m$ is an integer strictly between $k\sqrt{n^2+b+1}$ and $k\sqrt{n^2+b+2}$. For $n=b=1$ this means that $2\sqrt 3<m<4$, which is impossible. Therefore $n>1$. Define $\delta_{1,2}$ per $(1)$. Then by definition of $k$, we have $0<\delta_2\le 1$. Then from $(2)$ and $(4)$ $$m<k\sqrt{n^2+b+2}=1+nk+\underbrace{\delta_2(\sqrt{n^2+b+2}-n)}_{\in(0,1)}$$ so that $m\le 1+nk$. Using $(2)$ again we get $$1+nk\ge m>k\sqrt{n^2+b+1}=1+nk+\delta_1(\sqrt{n^2+b+1}- n)$$ so that $\delta_1(\sqrt{n^2+b+1}- n)<0$ and by $(3)$ ultimately $\delta_1<0$. But $\delta_1<0<\delta_2$ is equivalent to $k$ being strictly between $\frac{n+\sqrt{n^2+b+2}}{b+2}$ and $\frac{n+\sqrt{n^2+b+1}}{b+1}$.$_\square$

• This is very helpful. I'd like to acknowledge your contribution in a paper I'm writing -- Can you contact me to discuss it? My email address can be found via the website listed in my profile page. – mweiss Apr 20 '15 at 17:29
• @mweiss Just a gentle reminder that you did not actually accept the answer. (It seems you might have intended to.) – David K May 24 '15 at 20:36