4
$\begingroup$

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.

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

1 Answer 1

3
+150
$\begingroup$

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$

$\endgroup$
2
  • 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, 2015 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, 2015 at 20:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .