## Solving a second Erdos-problem (!!)

Again: not happy about this post. It seems like I’m terrible at explaining my thoughts on paper. Well, it’s not as if I didn’t know that, but it’s worse than I thought. Anyway, solving two problems of Erdos and Graham in 24 hours is not something I’m not going to blog about;

In their book, Erdös and Graham also ask the following, I think more general, question:

Let $\displaystyle \sum_{i=a}^b \dfrac{1}{i} = \dfrac{u_{a,b}}{v_{a,b}}$. For fixed $a$ what is the least $b = b(a)$ such that $v_{a,b} < v_{a,b-1}$? In fact, is there always such a $b$ for every $a$? Using the result of the previous post, I am able to show that $b$ exists for every $a$, and, even more, $b \le 6a$ for all $a$. In a very strict sense this is best possible, as $b(1) = 6$. I will use the notation from the previous two posts, along with the new definition: $X_{a,b} = X_b - X_{a-1}*\dfrac{L_b}{L_{a-1}}$. We now have:

$\displaystyle \sum_{i = a}^b \dfrac{1}{i}$
$= \displaystyle \sum_{i = 1}^b \dfrac{1}{i} -$ $\displaystyle \sum_{i = 1}^{a-1} \dfrac{1}{i}$
$= \dfrac{X_b}{L_b}$ $- \dfrac{X_{a-1}}{L_{a-1}}$
$= \dfrac{X_{a,b}}{L_b}$

With $v_{a,b} = \dfrac{L_b}{(X_{a,b}, L_b)}$. Now, let $k$ be such that $3^k \le a < 3^{k+1}$. Let $b = 2*3^{k+1}$. Note that $L_b = L_{b-1}$ in that case. So we’re done if we can show $(X_{a,b}, L_b) > (X_{a, b-1}, L_{b-1})$. And the proof of this is not very hard using the result of the previous post;

$(X_{a, b}, L_b) = (X_b - X_{a-1} \dfrac{L_b}{L_{a-1}}, L_b)$ $= (X_{b-1} + \dfrac{L_b}{b} - X_{a-1} \dfrac{L_b}{L_{a-1}}, L_b)$

Now, the only difference with $(X_{a, b-1}, L_{b-1})$ is the term $\dfrac{L_b}{b}$. This term doesn’t affect anything, except for possibly factors of $2$ and $3$ (since $b = 2*3^k$). But we already know that $X_n$ is odd for all $n$, which implies $X_{a,b}$ is also odd for all $a,b$ with $b \ge 2a$. So the only thing that the term $\dfrac{L_b}{b}$ might change, is the divisibility of $X_{a,b}$ by $3$. And, indeed, we showed in the previous two posts that $(X_{b-1}, 3) = 1$ for $b = 2*3^k$, while $(X_b, 3) = 3$. So, since $3|\dfrac{L_b}{L_{a-1}}$ by our choice of $b$, $(X_{a, b-1}, 3) = 1$, while $(X_{a,b}, 3) = 3$. In other words: $3v_{a,b} \le v_{a, b-1}$, and this finishes our proof.
To recapture: Let $a$ be fixed. Let $k$ be such that $3^k \le a < 3^{k+1}$. Choose $b = 2*3^{k+1}$. Then: $v_{a,b} < v_{a,b-1}$