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.

  • $\begingroup$ 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 .. $\endgroup$ – Han de Bruijn Apr 19 '15 at 14:05
  • $\begingroup$ Nope, it's what I wrote. $\endgroup$ – mweiss Apr 19 '15 at 14:25

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$

  • 1
    $\begingroup$ 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. $\endgroup$ – mweiss Apr 20 '15 at 17:29
  • $\begingroup$ @mweiss Just a gentle reminder that you did not actually accept the answer. (It seems you might have intended to.) $\endgroup$ – David K May 24 '15 at 20:36

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.