Curious Number Theory Roadblock

[Poopsilon]

So basically I am trying to prove that the sum ∑1/2k from k=1 to n is a fraction of the form odd/even, that is to say that the denominator will contain more 2's than the numerator.

Now I'm almost positive this is true, and I suppose it might be more tractable to consider the stronger statement of taking the sum of some arbitrary set of fractions of the form 1/even and proving that that sum is a fraction of the form odd/even, ( although we would have to exclude the case of 1/2 + 1/2 and the others analogous to it ).

I actually want to prove this so I can prove a further statement and this step in my proof is really stumping me. Also note this isn't homework, its me satisfying my own personal interest in analytic number theory, so if you have any thoughts please don't feel the need to give cryptic overly ambiguous responses, thanks =].

 

[lanedance]

how about sum 1 to 2
= 1/2+1/4 = 2/4+1/4 = 3/4
then i'd attempt to generalise from here

 

[eczeno]

interesting, i would find a formula for the partial sums, then use induction to show it (if it is true, of course!). that is what i would try first, anyway.good luck.

 

[HallsofIvy]

For n= 3, this is 1/2+ 1/4+ 1/6= 6/12+ 3/12+ 2/12. For n= 4, 1/2+ 1/4+ 1/6+ 1/8= 12/24+ 6/24+ 4/24+ 3/24. For n= 5, 1/2+ 1/4+ 1/6+ 1/8+ 1/10= 60/120+ 30/120+ 20/120+ 15/120+ 12/120.

Obviously, the denominator is always even. And I would conjecture that, once the fractions have all been converted to that denominator, exactly one of the numerators will be postive: if n is odd, the next to last, if n is even, the last. Can you prove that?

 

[Poopsilon]

@eczeno: Induction does seem like a good idea to me as well, as the inductive assumption allows one to reduce the complexity of the problem considerably, unfortunately I'm not sure there exists a sequence of partial sums for this series, and doing induction with the series seems to lose some crucial bit of information along the way.

@HallsofIvy: (I'm assuming you meant to say odd not positive). Thats an interesting strategy, I think I will try that.

 

[Stephen Tashi]

Just some thoughts:

A sufficient induction hypothesis migh be:

\sum_{k=1}^{n} \frac{1}{2k} = \frac {P}{Q}

wiht P odd, Q even.

Use the abbreviation T(x) to mean "the power of two corresponding to the least significant non-zero digit of the base 2 representation of x".

T(P) = 0 (i.e. the last digit, base 2, of an odd number is 1, which corresponds to 2^0)

Let T(Q) = q, S = 2(n+1), T(S) = s

The induction step would involve evaluating
\frac{P}{Q} + \frac{1}{S} = \frac{PS + Q}{QS}

T(PS) = s,
T(PS + Q) <= 1 + min{q,s} ( if q = s then the powers could add to be one higher)
T(QS) = q + s.

Reducing factors of 2 from \frac{PS + Q}{QR} is accomplished by a divison that shifts the powers of 2, in the base 2 representation of the numbers, downward. If the maximum shift that can be made in numerator is less than the maximum shift that can be made in the denominator, the fraction will be reduced to the form odd-over-even. This will happen when 1 + min{q,s} < q + s.

 

[Poopsilon]

Ok so I solved it. Tashi I think my solution is along the same general line of reasoning as yours, although your argument definitely uses more advanced tools and I am unable to completely follow it.

I actually had to prove a subsidiary result first: that the set \left \{2,4,...,2n \right \} has a unique element containing a maximal number of 2&#039;s in its prime factorization, (provable by contradiction, and an interesting result in its own right). Then from there I wrote the series as:

\sum_{k=1}^{n} \frac{1}{2k} = \frac{\frac{LCM[2,4,...,2n]}{2} + \frac{LCM[2,4,...,2n]}{4} + ... + \frac{LCM[2,4,...,2n]}{2n}}{LCM[2,4,...2n]}.

Then by the definition of the Least Common Multiple, combined with my subsidiary result, all but one of those fractions sitting in the numerator has more 2&#039;s in its numerator than its denominator. Therefore in the numerator of the main fraction we have a bunch of even numbers plus one odd number giving us an odd number together with an even denominator.

What I actually needed this result for was to prove the final problem in chapter 1 of Apostol's Introduction to Analytic Number Theory. Which was to show that the series \sum_{k=1}^{n} \frac{1}{k} for n&gt;1 is never equal to an integer. What I did was split the series into two series, one producing the fractions with even denominators and the other producing the fractions with odd. Clearly the latter series produces a fraction with an odd denominator and so by proving that the former produces a fraction of the form \frac{odd}{even}, an elementary application of integer parity suffices to show that their sum is a fraction of the form \frac{odd}{even}

Anyways, some really good suggestions all around, thanks guys.