Author |
Topic: Sum of integer reciprocals (Read 8941 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Sum of integer reciprocals
« on: Jan 7th, 2003, 5:49am » |
 Quote  Modify
|
Show that the sum of the reciprocals of the first n positive numbers is not an integer for n > 1.
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Sum of integer reciprocals
« Reply #1 on: Jan 7th, 2003, 6:53am » |
Quote Modify
|
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
|
| « Last Edit: Jan 7th, 2003, 8:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: Sum of integer reciprocals
« Reply #2 on: Jan 7th, 2003, 2:16pm » |
Quote Modify
|
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.
|
| « Last Edit: Jan 7th, 2003, 2:21pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: Sum of integer reciprocals
« Reply #3 on: Jan 7th, 2003, 5:27pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Sum of integer reciprocals
« Reply #4 on: Jan 8th, 2003, 4:25am » |
Quote Modify
|
on Jan 7th, 2003, 5:27pm, 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 and a rather comprehensible statement of Erdos's proof.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Sum of integer reciprocals
« Reply #5 on: Jan 8th, 2003, 8:26pm » |
Quote Modify
|
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 Hn be the sum of the first n reciprocals. Also, let 2N be the largest power of 2 that is less than n. When you do the whole common denominator routine, every reciprocal except for 1/2N will end up with an even number as numerator. Therefore,
Hn = (even number + odd number)/2N *odd number,
which is clearly not an integer.
I wonder... could the fact that Hn is never an integer, coupled with Garzahd's earlier observations, yield a simple proof of Bertrand's postulate? Hmm.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Cyrus
Newbie
Gender:
Posts: 27
|
|
Re: Sum of integer reciprocals
« Reply #6 on: Jan 9th, 2003, 3:03pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: Sum of integer reciprocals
« Reply #7 on: Jan 9th, 2003, 4:57pm » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print