7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ How did you learn about the counterexample? Was it found by brute force? $\endgroup$ Mar 12, 2016 at 21:16
  • $\begingroup$ My friend told me $\endgroup$ Mar 12, 2016 at 22:00
  • $\begingroup$ @TheGreatDuck, have you got something in mind? How would you find a counterexample using what you wrote? $\endgroup$
    – Τίμων
    Mar 13, 2016 at 22:03

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2016 at 12:07
  • $\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, 2016 at 7:50

You must log in to answer this question.

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