Updated: finding an integer $k$ that minimizes $1/(N-k) (1+1/k)$

Question

For any positive integer $N$ and real number $a > 0$. Define $f(k) = \frac{1}{N-k} (1+\frac{a}{k})$. The problem is to find a positive integer $k$ that minimizes $f(k)$.

It is quite easy to solve the problem by finding the minimum $k$ satisfying $f(k)\leq f(k+1)$, this will give a solution $k^* = \lceil \sqrt{aN+a^2 + 1/4} - a - 1/2 \rceil$, which is fine.

On the other hand, one can assume $k$ takes continuous values, minimizing $f(k)$ gives $\sqrt{aN+a^2} - a$, we then round this to the nearest integer and get $[\sqrt{aN+a^2} - a]$.

Since it is derived from continuous approximation, $[\sqrt{aN+a^2} - a]$ is not necessarily the correct. However, from numerical simulation, I found that $[\sqrt{aN+a^2} - a]$ is always the correct answer (meaning that it always equals $\lceil \sqrt{aN+a^2 + 1/4} - a - 1/2 \rceil$. )

So my problem is to prove (or disprove) $\lceil \sqrt{aN+a^2 + 1/4} - a - 1/2 \rceil = [\sqrt{aN+a^2} - a]$. I already proved that it is true when $a$ is also an integer, but not quite sure what is the case when $a$ is not an integer.

Any thoughts?

ps. sorry if you see this post twice. I posted this question before, but without detailed explaining.

Answer 1

Part 1. (the proof that rounding functions may be different).

This is not true in general. Observe that $\frac{1}{2}>\left(\sqrt{a^2+Na}-a\right)-\left(\sqrt{a^2+Na+\frac{1}{4}}-a-\frac{1}{2}\right)>0.$ So it is enough to choose integer $m,$ to satisfy the $$\sqrt{a^2+Na}-a>m+\frac{1}{2}$$ and $$\sqrt{a^2+Na+\frac{1}{4}}-a-\frac{1}{2}< m+\frac{1}{2}.$$ First inequality is equivalent to

$$a >\frac{(m+\frac{1}{2})^2}{N-2m-1},$$ and the second one is equivalent to $a<\frac{m^2+2m+\frac{3}{4}}{N-2m-2},$ provided $N>2m+2.$ Now since the upper bound is clearly greater than the lower bound, one can choose $a$ to satisfy both inequalities.

Part 2. ( the proof that rounding function and the ceiling function might be different).

This is close to obvious if you use $\frac{1}{2}>\left(\sqrt{a^2+Na}-a\right)-\left(\sqrt{a^2+Na+\frac{1}{4}}-a-\frac{1}{2}\right)>0.$ Indeed, let $\sqrt{a^2+Na}-a=m+\alpha,$ where $m$ is an integer part. Then, if $\alpha\ge \frac{1}{2},$ both sides are indeed the same and equal to $m+1.$

If $\alpha<\frac{1}{2},$ then both sides have to be equal to $m.$ In other words, we must have $$\sqrt{a^2+Na+\frac{1}{4}}-a-\frac{1}{2}\le m,$$

as long as $$m <\sqrt{a^2+Na}-a< m+\frac{1}{2}.$$ However, our double inequality is equivalent to $$\frac{m^2}{N-2m}< a< \frac{(m+\frac{1}{2})^2}{N-2m-1}.$$

The condition $$\sqrt{a^2+Na+\frac{1}{4}}-a-\frac{1}{2}\le m,$$ is equivalent to $$a\le\frac{m^2+m}{N-2m-1}.$$ Clearly, since it is less than the upper bound for $a$ obtained above, one can choose $a,$ such that the last inequality fails.