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}


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: