14
$\begingroup$

I spotted a pattern while trying to generalize a problem. (EDIT: said problem has been removed from this post to avoid confusion. EDIT(2): Here is the problem again: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=367432&sid=356f2a2b519ab007bb648bf00e84934d#p367432 ) <--- That isnt the problem I want to solve, it is just where I got the pattern below from. I know how to solve the problem in the link already; I am only here trying to solve the problem below:

Here is the pattern I found, which I cannot prove. If you prove this, you win the bounty, and if there are multiple proofs, the most detailed (including extra information, etc) wins:

If $$\{k:k\in \mathbb{Z}^+,k\ne 4, k\ge 3\}$$,

$$\max\left\{\left(\frac{k}{\lfloor \frac{k}{\text{e}}\rfloor }\right)^{\lfloor \frac{k}{{\text{e}}}\rfloor},\left(\frac{k}{\lceil \frac{k}{\text{e}}\rceil }\right)^{\lceil \frac{k}{{\text{e}}}\rceil}\right\}=\begin{cases}\left(\frac{k}{\lfloor \frac{k}{\text{e}}\rfloor }\right)^{\lfloor \frac{k}{{\text{e}}}\rfloor}\quad\text{if}\ \{\frac{k}{\text{e}}\}<0.5\\ \\\left(\frac{k}{\lceil \frac{k}{\text{e}}\rceil }\right)^{\lceil \frac{k}{{\text{e}}}\rceil}\quad\text{if}\ \{\frac{k}{\text{e}}\}\ge 0.5\end{cases}$$.

I honestly don't know where to begin.

EDIT: Here $\{x\}$ denotes the fractional part of $x$, e.g. $\{5.4\}=0.4$.

$\endgroup$
  • $\begingroup$ What for? What is a possible use of that $\max$? Isn't it art for art's sake? $\endgroup$ – user64494 Sep 11 '14 at 4:03
10
+500
$\begingroup$

Your conjecture is correct for $k$ sufficiently large and, almost surely, the only counterexample is the case $k=4$ you have already noted. This inequality is insanely tight: In the end, it comes down to the fact that $e/6 < 1/2$ and some very fortunate coincidences concerning the continued fraction of $e$.

We put $n = \lfloor k/e \rfloor$. We have $$\left( \frac{k}{n} \right)^n < \left( \frac{k}{n+1} \right)^{n+1}$$ if and only if $$(n+1)^{n+1}/n^n < k.$$ We'll set $c=(n+1)^{n+1}/n^n$.

On the other hand, $\{ k/e \} > 1/2$ is equivalent to $k/e>n+1/2$, or $k>e(n+1/2)$. So your conjecture is $$k> c \Longleftrightarrow k > e(n+1/2).$$ In other words, if you had a counterexample to your conjecture, there would be an integer $k$ between $c$ and $e(n+1/2)$. We'll rule this out.

To this end, I need to replace $c$ by something more convenient. I claim that $e(n+1/2) > c>e (n+1/2-1/(23.9 (n+1/2)))$ for $n \geq 4$. This is definitely true for $n$ sufficiently large, as $$c = n \exp((n+1) \log(1+1/n)) = n \exp((n+1) (1/n-1/(2n^2) + 1/(3 n^3)+O(1/n^4)))$$ $$= e(n+1/2-1/(24 n) + O(1/n^2))$$ I also checked it for $4 \leq n \leq 100$. I haven't done the careful work of figuring out the constant in the $O()$ to prove this for all $n$, but you could if you needed to and, if I am wrong, it only introduces finitely many errors. (Here and in the following, you should think of numbers like $23.9$ as "essentially $24$", but I have put in a little fudge to make the inequalities true inequalities rather than asymptotics.)

Our goal is to show that there are no solutions to $$e(n+1/2-1/(23.9 (n+1/2))) < k < e(n+1/2)$$ in integers, except for $k=4$ and $n=1$ (as already noted). We can already see that, if there are any solutions, they are rare: you need to get an interval of length $1/(24 n)$ to contain an integer. We will actually see that there aren't any.

Applying $x \mapsto e-x/(n+1/2)$ to each term, this equation is equivalent to: $$\frac{e}{23.9 (n+1/2)^2} > e-\frac{2k}{2n+1} > 0$$ or $$\frac{e}{5.975 (2n+1)^2} > e-\frac{2k}{2n+1} > 0 \quad (\ast).$$

We now remember a theorem about continued fractions (see, for example, Theorem 184 in Hardy and Wright): If $x$ is irrational and $p$ and $q$ are integers with $$\left| x - \frac{p}{q} \right| < \frac{1}{2 q^2}$$ then $p/q$ is a convergent of $x$. Since $e/5.975 < 1/2$, if we had a solution to $(\ast)$, then $(2k)/(2n+1)$ would be a convergent of $e$. (Since convergents grow exponentially fast, this already proves that solutions to $(\ast)$ are very rare.) Roughly, the rest of the proof is as follows: If you look at the convergents $p_i/q_i$ of $e$ and compute $q_i^2 |e-p_i/q_i|$ you'll see that it is approaching $1/2$ for $i \equiv 1, 3 \bmod 3$ and going to zero for $i \equiv 2 \bmod 3$. Since $1/2 > e/5.975$, we don't expect any solutions in the first case. In the second case, it happens that $p_i/q_i$ is of the form $\mbox{odd}/\mbox{odd}$, not $(2k)/(2n+1)$. The rest of the argument is filling in the details of this.

We recall the basic formulas of the theory of continued fractions: If $x = a_0+1/(a_1+1/(a_2+1/(a_3 + \cdots))) =: [a_0, a_1, a_2, a_3, \cdots]$ and the convergents of $x$ are $p_1/q_1$, $p_2/q_2$, etcetera, than $p_{i+1} = a_i p_i +p_{i-1}$ and $q_{i+1} = a_i q_i + q_{i-1}$.

The continued fraction of $e$ is known: $$e = [2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,\cdots].$$ From now on, $a_i$ will denote the sequence $2$, $1$, $2$, $1$, $1$, $4$, etcetera and $p_i/q_i$ will denote the convergents, starting $p_1/q_1=2/1$, $p_2/q_2 = 3/1$, $p_3/q_3=8/3$, $p_4/q_4 = 11/4$, etcetera. (Note that $8/3$ corresponds to $k=4$, $n=1$.)

From the relations $p_{i+1} = a_i p_i +p_{i-1}$ and $q_{i+1} = a_i q_i + q_{i-1}$, we check that the parity of $(p_i, q_i)$ repeats with period $6$. The terms of the form $(2k)/(2n+1)$ are appear in positions that are $1$ or $3$ modulo $6$, starting $$2, \ 8/3,\ 106/39,\ 1264/465,\ 25946/9545,\ 517656/190435, \cdots$$ I checked the $4$ convergents after $8/3$ explicitly and they did not violate $(\ast)$, so I can assume that I am dealing with some quite large numbers if there are any counterexamples.

We have the alternating sum $\left| e-p_i/q_i \right| = 1/(q_i q_{i+1}) - 1/(q_{i+1} q_{i+2})+ \cdots$ and thus, in particular, $\left| e-p_i/q_i \right| > 1/(q_i q_{i+1}) - 1/(q_{i+1} q_{i+2})$. In the cases we care about, $e>p_i/q_i$ so we can drop the absolute value.

Case 1: $i=1 \bmod 6$, like $106/39$. Note that the denominators surrounding $39$ are $7$, $32$, $39$, $71$, $495$. $$\frac{1}{q_i q_{i+1}} - \frac{1}{q_{i+1} q_{i+2}} = \frac{1}{q_i (2 q_{i} - q_{i-2})} - \frac{1}{q_{i+1} q_{i+2}}.$$ But $q_{i-2}/q_i$ and $q_i/q_{i+2} \to 0$ as $i \to \infty$ while $1 \bmod 6$ (these are $7/39$ and $39/495$ in the example), so $$q_i^2 \left( \frac{1}{q_i (2 q_{i} - q_{i-2})} - \frac{1} {q_{i+1} q_{i+2}} \right) \to 1/2.$$ Already $i=13$ gets you past $e/5.975$, so there are no solutions in this case.

Case 2: $i \equiv 3 \bmod 6$, like $1264/465$. Note that the denominators surrounding $465$ are $71$, $465$, $536$, $1001$. In this case, we have $$\frac{1}{q_i q_{i+1}} - \frac{1}{q_{i+1} q_{i+2}} =\frac{1}{q_i q_{i+1}} - \frac{1}{q_{i+1}(q_i+ q_{i+1})} = \frac{1}{q_i (q_i+q_{i+1})} = \frac{1}{q_i (2 q_i + q_{i-1})}.$$ Again, $q_{i-1}/q_{i} \to 0$ (this is $71/465$ in the example) so $$q_i^2 \frac{1}{q_i (2 q_i + q_{i-1})} \to 1/2.$$ Taking $i=9$ already gets you past $e/5.975$.

$\endgroup$
  • $\begingroup$ One point glossed in the above: The hypothetical $(2k)/(2n+1)$ obeying $(\ast)$ might not be in lowest terms; suppose $(2k)/(2n+1)=p/q$ with $GCD(p,q)=1$. But, if $|e-(2k)/(2n+1)|<e/(5.975 (2n+1)^2)$ then also $|e-p/q|<e/(5.975 q^2)$. And $GCD(2k, 2n+1)$ would be odd, so we would have $p$ even and $q$ odd. So we could replace $(2k,2n+1)$ by $(p,q)$ and then run the above argument. $\endgroup$ – David E Speyer Sep 11 '14 at 3:54
5
$\begingroup$

Not an answer, just an observation - hence CW.

The plot of

$\text{max} \begin{cases} \dfrac{e}{k}\log\left(\dfrac{k}{\lfloor k/e\rfloor}^{\lfloor k/e\rfloor}\right)\\ \\ \dfrac{e}{k}\log\left(\dfrac{k}{\lceil k/e\rceil}^{\lceil k/e\rceil}\right)\\ \end{cases}$

against background $\mod \dfrac{e}{2}$

enter image description here

shows that what you conjecture is not strictly true, but it certainly approaches that limit (if I have understood the problem correctly).

Update

For $e\pm\frac{1}{2}$, fractional part $\pm\frac{1}{4}$:

enter image description here

Manipulate[s = E + m; pr2 = 1.005; pr1 = 0.94; r1 = s; c = m/E;Show[Plot[{If[FractionalPart[k/s] < 0.5 - m/2, 1.1, 0], 1}, {k, r1, (r1 + 5 s)}, PlotStyle -> {{Opacity[0]}, {Opacity[0]}},Filling -> {1 -> {2}}, FillingStyle -> {Opacity[0.2]},Frame -> True, Axes -> False, GridLines -> {{}, {1}},GridLinesStyle -> {Gray, Dashing[0.01]},PlotRange -> {{r1, (r1 + 5 s)}, {pr1, pr2}}], Plot[{If[Log[(k/Floor[k/s])^Floor[k/s]]/(k/s) - c >Log[(k/Ceiling[k/s])^Ceiling[k/s]]/(k/s) - c,Log[(k/Floor[k/s])^Floor[k/s]]/(k/s) - c, I],If[Log[(k/Ceiling[k/s])^Ceiling[k/s]]/(k/s) - c >Log[(k/Floor[k/s])^Floor[k/s]]/(k/s) - c,Log[(k/Ceiling[k/s])^Ceiling[k/s]]/(k/s) - c, I]}, {k,r1, (r1 + 5 s)}, PlotStyle -> {{Red, Thick}, {Blue, Thick}}, Frame -> True,Axes -> False, PlotRange -> {{r1, (r1 + 5 s)}, {pr1, pr2}}]], {{m, 0}, -0.5, 0.5}]
$\endgroup$
  • 1
    $\begingroup$ No - $n\mod e/2-\epsilon $ $\endgroup$ – martin Sep 10 '14 at 4:16
  • 1
    $\begingroup$ ... look carefully at the plot - the stripes and the curves don't match up exactly. $\endgroup$ – martin Sep 10 '14 at 4:20
  • 1
    $\begingroup$ ... which is probably why you said in the question $ k \neq 4$ $\endgroup$ – martin Sep 10 '14 at 4:39
4
$\begingroup$

Not an answer, but an approach: Fix a $k$ and let $K := \lceil \frac{k}{e} \rceil$. Suppose $\left\{ \frac{k}{e} \right\} \ge \frac12$. We want to show that \begin{align*} \left(\frac{k}{\lfloor \frac ke \rfloor}\right)^{\lfloor \frac ke \rfloor} \le \left(\frac{k}{\lceil \frac ke \rceil}\right)^{\lceil \frac ke \rceil} \end{align*} Basic transformations (and the fact that $K = \lceil \frac ke \rceil = \lfloor \frac ke \rfloor + 1$) yield the equivalent inequality \begin{align*} K^K \le k \cdot (K - 1)^{K - 1} \end{align*} Now our assumption $\left\{ \frac{k}{e} \right\} \ge \frac12$ means $\frac ke \ge \lfloor \frac ke \rfloor + \frac 12 = K - \frac 12$. Hence \begin{align*} k \cdot (K - 1)^{K - 1} \ge e \cdot \left(K - \frac12\right) \cdot (K - 1)^{K - 1} \end{align*} Plugging this in above and transforming, we see that it is sufficient to show that \begin{align*} \left(\frac{K}{K-1}\right)^K \le e \cdot \frac{K - \frac12}{K - 1} \end{align*} Taking the reciprocal and multiplying by $e$, we get the equivalent inequality \begin{align*} \left(1 - \frac1K\right)^K \cdot e \ge \frac{K - 2}{K - 1} \end{align*} Both sides converge to $1$ as $K \to \infty$ (here the role of the constant $e$ becomes apparent).

If we want to prove the other case, i. e., $\left\{ \frac ke \right\} < \frac12$, we analogously arrive at \begin{align*} \left(1 - \frac1K\right)^K \cdot e < \frac{K - 2}{K - 1} \end{align*}

I could not proceed from here since I don't know enough about the convergence of $(1+\frac xn)^n$. I am not even sure whether this helps at all, but I wanted to post it since it explains where the $e$ comes from.

$\endgroup$

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.