Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
You could have edited your first question. -- Posting questions twice is, say, not recommended. –  Stefan Kohl May 24 '13 at 9:17

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Hi Safoura, thanks for your answer. But there is some problem here. Note that I have $k^* = \lceil \sqrt{aN+a^2 + 1/4} - a - 1/2 \rceil$, where $\lceil x \rceil$ is the ceiling function, denotes the smallest integer no less than $x$. While $k^* = [\sqrt{aN+a^2} - a]$, where $[x]$ is the rounding function, the integer closest to $x$. So your proof seems do not apply ... –  user34318 May 24 '13 at 20:41
    
sorry, my vision betrays me... I have edited the post accordingly to include the case you were asking for. –  Alvin May 24 '13 at 21:53
2  
Perhaps I am also not seeing things. Why is the answer not k=N+1? Gerhard "Someone Make A Constraint Visible" Paseman, 2013.05.24 –  Gerhard Paseman May 24 '13 at 22:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.