wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Sum of integer reciprocals
        
(Message started by: NickH on Jan 7^th, 2003, 5:49am)

Title: Sum of integer reciprocals
Post by NickH on Jan 7^th, 2003, 5:49am

Show that the sum of the reciprocals of the first n positive numbers is not an integer for n > 1.

Title: Re: Sum of integer reciprocals
Post by towr on Jan 7^th, 2003, 6:53am

for others who, like me, have no idea what a reciprocal is:
http://mathworld.wolfram.com/Reciprocal.html

In other words the question is to prove
http://tcw2.ppsw.rug.nl/~towr/PHP/formula.php?formula=%5Csum_%7Bi%3D1%7D%5En+i%5E%7B-1%7D%0D%0A%5Cnot%0D%0A%5Cin+%7B%5Crm+I%5C%21N%7Efor%7E%7D%0D%0An+%3E+1%0D%0A%0D%0A+

Title: Re: Sum of integer reciprocals
Post by william wu on Jan 7^th, 2003, 2:16pm

Stuck.

I thought about getting common denominators, adding up the fractions, and trying to show that the numerator is never a multiple of the common denominator. Also thought about mathematical induction.

It's a well known fact that the sum of the reciprocals of the first n integers approaches ln(n) as n gets large, but I dunno if that helps at all.

Title: Re: Sum of integer reciprocals
Post by Garzahd on Jan 7^th, 2003, 5:27pm

Pick a prime p.

1 + 1/2 + 1/3 + ... + 1/p is pretty clearly not an integer. Proof, in case that's too handwavy: Assume it is an integer, and we can make a common denominator as follows:
(p! + p!/2 + p!/3 + ... p!/(p-1) + (p-1)! ) / p!
All terms of the numerator are divisible by p except for the last one which isn't (because p is prime, duh). Therefore the numerator isn't divisible by p and can't be divisible by p!.

Now, fixing p, we can prove 1 + 1/2 + ... + 1/x is not an integer for p <= x <= 2p-1, by the same argument... the numerator of the common-denominator-expression contains exactly one term that's not divisible by p, therefore the sum of the numerator isn't divisible by p and the fraction isn't an integer.

And I'm very confident (though not sure how to prove) that there's always another prime in x's range, so therefore we've hit all integers.

Title: Re: Sum of integer reciprocals
Post by wowbagger on Jan 8^th, 2003, 4:25am

on 01/07/03 at 17:27:44, Garzahd wrote:

And I'm very confident (though not sure how to prove) that there's always another prime in x's range, so therefore we've hit all integers.

When reading this I immediately thought that I'd already seen a proof of this. Luckily, I found it again after a little searching:

Maybe you're interested in Bertrand's Postulate (http://mathworld.wolfram.com/BertrandsPostulate.html) and a rather comprehensible statement of Erdos's proof (http://mathforum.org/library/drmath/view/51527.html).

Title: Re: Sum of integer reciprocals
Post by Pietro K.C. on Jan 8^th, 2003, 8:26pm

Very insightful beginning of proof by Garzahd! I loved it. And yes, it's true that, for every integer x, there is a prime between x and 2x.

I've come up with what is perhaps a simpler proof on the whole, though, because, as I recall, Bertrand's postulate is a handful to demonstrate. It goes as follows.

Let n be any integer and let H_n be the sum of the first n reciprocals. Also, let 2^N be the largest power of 2 that is less than n. When you do the whole common denominator routine, every reciprocal except for 1/2^N will end up with an even number as numerator. Therefore,

H_n = (even number + odd number)/2^N *odd number,

which is clearly not an integer.

I wonder... could the fact that H_n is never an integer, coupled with Garzahd's earlier observations, yield a simple proof of Bertrand's postulate? Hmm.

Title: Re: Sum of integer reciprocals
Post by Cyrus on Jan 9^th, 2003, 3:03pm

I always feel like a complete moron when I read these types of threads. :(

You guys say things like "pretty clearly . . . ." or "it's a well known fact that . . . ." followed by some complex, obscure (to ME anyways) formula I've never even HEARD of.

But I still try to read through the different posts and figure out how you guys thought about the problem even if I don't understand the math you used to get the answer.

So, just lettin' ya all know, you're geniuses and obviously know your math, but if you could explain how you thought about the question (example: willywu's first post on this thread) and the steps you took to think of a proof, that would be awesome. Then maybe one day I can at least think about the problems in a similar manner to you even if I don't know the details or math of solving them.

Yours Truly,
Average Joe Idiot

Title: Re: Sum of integer reciprocals
Post by Garzahd on Jan 9^th, 2003, 4:57pm

Good point, Cyrus. I'll try explaining how I came to my answer, though I apologize if my thought process sounds strange.....

In fact, when I typed my "...pretty clearly not an integer" line from my previous post, I wasn't fully sure whether it required a proof because it seemed so intuitively apparent to me (Of course it does require proof, but I had a bit more thinking to do after I wrote that line.)

But why did it seem intuitively apparent to me? That's harder to answer. I began thinking about a contradiction-based proof, where we assume that the series is valiantly trying to become an integer and proving why that can't happen.

The gut instinct that led to the "intuitive" assertion was asking myself, "Okay, for which x is 1/x likely to mess up the quest for 1 + 1/2 + 1/3 + ... 1/x trying to become an integer?" The first number that popped into my mind was 7, since 1/7 has the ugly decimal representation .1428571428... which is unlikely to be rectified into an integer by most fractions unless they *also* contain a factor of 7 in their denominator.

From the ugly-decimal idea I generalized pretty quickly that primes were the culprit, and from the factors-of-7 idea I generalized that a particular prime would ruin the quest-to-become-an-integer for everything from p to 2p.

Then, I began translating into mathematical expressions that would actually be meaningful, instead of gut instincts and long decimals. Going back to the contradiction idea, I asked myself how I would put a square peg in a round hole by making 1 + 1/2 + ... + 1/p into an integer.

(A side note... if you encounter a problem that seems to accept a strange-looking statement as unilaterally true, take some time to convince yourself why they're saying this, even if it's not leading directly toward an answer to the question asked. You'll either learn something useful in the process, or you'll arrive at the correct specific clarification to ask about. One of my college problem-solving courses began many of its problems by saying "X is true. Convince yourself why X is true, then answer Y." I sometimes use the same strategy helping people in board/card games: I show the correct move, after it's clear the person hasn't figured it out, then ask them to convince themself why that's correct.) But back to the matter at hand...

For an arbitrary p, not necessarily 7, the only way I could force the series to be an integer is to make a common denominator (grade school fraction addition). Since I knew from earlier instinct that the 1/p term in particular was souring the water somehow, I paid particular attention to that in the expansion and saw that it was the only part missing a factor of p (see previous post). Right here was where everything clicked and I could plot out the way the rest of the proof would go.

I frequently find "talking it out" in the reply window to be a useful problem-solving mechanism. Nearly all my partial-solution posts are made this way.

Hope this helps...