A friend of mine asked me to prove or disprove that:

$$ \left\lceil\frac{2}{2^{1/n}-1}\right\rceil=\left\lfloor\frac{2n}{\ln 2}\right\rfloor \forall n \in \mathbb{Z^+} $$

First of all, I run a python code to numerically compute the values upto $5000$ in order to conjecture about the truth of proposition. I got a positive result. Then I tried plotting to get a rough idea about the behavior of functions, the conjecture seemed to be true. Nonetheless, I couldn't prove it. Now I am really frustrated to know that the first counter example is $777,451,915,729,368$.

Is an existential proof possible without brute force?

  • $\begingroup$ How did you learn about the counterexample? Was it found by brute force? $\endgroup$ – Matt Samuel Mar 12 '16 at 21:16
  • $\begingroup$ My friend told me $\endgroup$ – Hashir Omer Mar 12 '16 at 22:00
  • $\begingroup$ I think it is helpful to note that negating the inside of ceiling and also the outside of ceilingng at the same time make it change to flood. Perhaps that will yield something. Also remember the greater than less than identity for floor. That might help too. $\endgroup$ – The Great Duck Mar 13 '16 at 8:32
  • $\begingroup$ @TheGreatDuck, have you got something in mind? How would you find a counterexample using what you wrote? $\endgroup$ – Τίμων Mar 13 '16 at 22:03
  • $\begingroup$ I don't know really. I'm just thinking that maybe putting them both in terms of floor might allow one to combine them somehow. Ultimately we want a contradiction in algebra so my gut tells me we need to reduce the equation and solve for x. $\endgroup$ – The Great Duck Mar 13 '16 at 22:42

I read about this problem some time ago...
You can easily see that the difference $$\frac{2n}{\ln 2} - \frac{2}{2^{\frac{1}{n}}-1} $$ is increasing and getting closer to one. If $\frac{2n}{\ln 2}$ is smaller than a certain integer $k$, but close enough to $k$ so that $\frac{2}{2^{1/n}-1}$ is greater than $k-1$, then you have found a counterexample. But asking for a $n$ such that $\frac{2n}{\ln 2}$ is well enough approximated by $k$ is the same as asking for a good enough rational approximation $\frac{k}{n}$ of $\frac{2}{\ln 2}$. The convergents of the continued fraction of $\frac{2}{\ln 2}$ are the best approximations you can get. You just have to calculate them until you reach a counterexample, and you'll probably have to compute just tens of convergents, not billions. $777,451,915,729,368$ should be the denominator of one of these convergents.

  • $\begingroup$ But how do you know that that difference can be used? $\endgroup$ – The Great Duck Mar 13 '16 at 8:31
  • $\begingroup$ @TheGreatDuck I cannot really see what you mean... If you use it, you know that a counterexample occurs only when $ k−1<\frac{2}{2^{1/n}−1}<\frac{2n}{\ln 2}<k $, for some naturals kk and nn. $\endgroup$ – Τίμων Mar 13 '16 at 12:07
  • $\begingroup$ But what work do you perform to obtain that difference. How do you know that you can remove floor like that? Floors inverse does not exist and it wouldn't result in the original formula so how do you determine that the difference is useful. $\endgroup$ – The Great Duck Mar 13 '16 at 22:36
  • $\begingroup$ I am not removing floor and ceiling, I am just considering that difference... I did not obtain it, I just wrote it... The importance of knowing that difference is that you can thus see that there are only two possible cases: $k−1<\frac{2}{2^{1/n}−1}<\frac{2n}{\ln 2}<k$ and $k−1<\frac{2}{2^{1/n}−1}<k<\frac{2n}{\ln 2}<k+1$ for some naturals $k$ and $n\ge2$. In the latter case $\left\lceil\frac{2}{2^{1/n}−1}\right\rceil=k=\left\lfloor\frac{2n}{\ln 2}\right\rfloor$. In the former $\left\lceil\frac{2}{2^{1/n}−1}\right\rceil=k,\ \left\lfloor\frac{2n}{\ln 2}\right\rfloor=k-1$. $\endgroup$ – Τίμων Mar 14 '16 at 7:50

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.