FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Undergraduate
Proof that sum 1/k from 1...n isn't an integer for n > 1
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Patrick
science forum addict


Joined: 01 Feb 2006
Posts: 55

PostPosted: Mon Jun 12, 2006 6:42 am    Post subject: Proof that sum 1/k from 1...n isn't an integer for n > 1 Reply with quote
Hi, could you comment on this, on mistakes and
ways to improve it and show the best way, of course!

First, a lemma.

(*) If a prime p evenly divides all but one term of the sum

S = x_1 + x_2 + ... + x_n

then p doesn't evenly divide S.

Proof of (*)

Let S = x_1 + x_2 + ... + x_n and wlog let x_n be
the term not divisible by p.

Since the first (n - 1) terms are divisible by p,
for some integer k they factor into:

p*k = x_1 + x_2 + ... + x_(n-1)

Now if S = (p*k + x_n) is evenly divisible by p it
can be factored as S = p*(k + x_n') where p*x_n' = x_n,
contradicting the hypothesis that p doesn't evenly
divide x_n. So p must not evenly divide S.


Proposition: sum[k=1 to n] 1/k isn't an integer for n > 1.

Proof of Proposition:

sum[k=1 to n] 1/k = 1/1 + 1/2 + 1/3 + ... + 1/(n - 1) + 1/n

Since n > 1 showing that this sum isn't integer is
equivalent to showing that the sum minus 1 isn't
an integer so remove the first term leaving:

1/2 + 1/3 + ... + 1/(n - 1) + 1/n

Now multiply each kth term in the sum above by
the fraction (n!/(k + 1)) / (n!/(k + 1)) to obtain

[ (n!/2) + (n!/2) + ... + (n!/(n - 1)) + (n!/n) ] / n!

Let p be the largest prime less than n, this prime exists
because n is at least 2. Since p is a factor of n! and
does not evenly divide the pth term in the numerator,
it follows from (*) that p does not evenly divide the
numerator. Therefore the sum can't be an integer.



Thanks.
Back to top
José Carlos Santos
science forum Guru


Joined: 25 Mar 2005
Posts: 1111

PostPosted: Mon Jun 12, 2006 12:56 pm    Post subject: Re: Proof that sum 1/k from 1...n isn't an integer for n > 1 Reply with quote
On 12-06-2006 7:42, Patrick wrote:

Quote:
First, a lemma.

(*) If a prime p evenly divides all but one term of the sum

S = x_1 + x_2 + ... + x_n

then p doesn't evenly divide S.

Proof of (*)

Let S = x_1 + x_2 + ... + x_n and wlog let x_n be
the term not divisible by p.

Since the first (n - 1) terms are divisible by p,
for some integer k they factor into:

p*k = x_1 + x_2 + ... + x_(n-1)

Now if S = (p*k + x_n) is evenly divisible by p it
can be factored as S = p*(k + x_n') where p*x_n' = x_n,
contradicting the hypothesis that p doesn't evenly
divide x_n. So p must not evenly divide S.


Proposition: sum[k=1 to n] 1/k isn't an integer for n > 1.

Proof of Proposition:

sum[k=1 to n] 1/k = 1/1 + 1/2 + 1/3 + ... + 1/(n - 1) + 1/n

Since n > 1 showing that this sum isn't integer is
equivalent to showing that the sum minus 1 isn't
an integer so remove the first term leaving:

1/2 + 1/3 + ... + 1/(n - 1) + 1/n

Now multiply each kth term in the sum above by
the fraction (n!/(k + 1)) / (n!/(k + 1)) to obtain

That's a complicated way of expressing it. You could just say
that the previous sum is clearly equal to the following one.

Quote:
[ (n!/2) + (n!/2) + ... + (n!/(n - 1)) + (n!/n) ] / n!

You mean n!/3 instead of the second n!/2

Quote:
Let p be the largest prime less than n, this prime exists
because n is at least 2. Since p is a factor of n! and
does not evenly divide the pth term in the numerator,
it follows from (*) that p does not evenly divide the
numerator. Therefore the sum can't be an integer.

There's a problem here. How do you know that _p_ does not divide evenly
the p-th term in the numerator? First of all, my guess is that you mean
(p - 1)-th term here. Anyway, what you're saying is that _p_ does not
divide evenly n!/p. Why? Suppose that n >= 2p; then it is not true that
_p_ does divide evenly n!/p.

Best regards,

Jose Carlos Santos
Back to top
Patrick
science forum addict


Joined: 01 Feb 2006
Posts: 55

PostPosted: Mon Jun 12, 2006 2:44 pm    Post subject: Re: Proof that sum 1/k from 1...n isn't an integer for n > 1 Reply with quote
José Carlos Santos wrote:
Quote:
On 12-06-2006 7:42, Patrick wrote:

First, a lemma.

(*) If a prime p evenly divides all but one term of the sum

S = x_1 + x_2 + ... + x_n

then p doesn't evenly divide S.

Proof of (*)

Let S = x_1 + x_2 + ... + x_n and wlog let x_n be
the term not divisible by p.

Since the first (n - 1) terms are divisible by p,
for some integer k they factor into:

p*k = x_1 + x_2 + ... + x_(n-1)

Now if S = (p*k + x_n) is evenly divisible by p it
can be factored as S = p*(k + x_n') where p*x_n' = x_n,
contradicting the hypothesis that p doesn't evenly
divide x_n. So p must not evenly divide S.


Proposition: sum[k=1 to n] 1/k isn't an integer for n > 1.

Proof of Proposition:

sum[k=1 to n] 1/k = 1/1 + 1/2 + 1/3 + ... + 1/(n - 1) + 1/n

Since n > 1 showing that this sum isn't integer is
equivalent to showing that the sum minus 1 isn't
an integer so remove the first term leaving:

1/2 + 1/3 + ... + 1/(n - 1) + 1/n

Now multiply each kth term in the sum above by
the fraction (n!/(k + 1)) / (n!/(k + 1)) to obtain

That's a complicated way of expressing it. You could just say
that the previous sum is clearly equal to the following one.

[ (n!/2) + (n!/2) + ... + (n!/(n - 1)) + (n!/n) ] / n!

You mean n!/3 instead of the second n!/2

Yes.

Quote:
Let p be the largest prime less than n, this prime exists
because n is at least 2. Since p is a factor of n! and
does not evenly divide the pth term in the numerator,
it follows from (*) that p does not evenly divide the
numerator. Therefore the sum can't be an integer.

There's a problem here. How do you know that _p_ does not divide evenly
the p-th term in the numerator? First of all, my guess is that you mean
(p - 1)-th term here.

Yes, I meant (p - 1).

Quote:
Anyway, what you're saying is that _p_ does not
divide evenly n!/p. Why? Suppose that n >= 2p; then it is not true that
_p_ does divide evenly n!/p.

You're right. Can I get a hint for a good way to do this proof.

Thanks.
Back to top
José Carlos Santos
science forum Guru


Joined: 25 Mar 2005
Posts: 1111

PostPosted: Mon Jun 12, 2006 3:12 pm    Post subject: Re: Proof that sum 1/k from 1...n isn't an integer for n > 1 Reply with quote
On 12-06-2006 15:44, Patrick wrote:

Quote:
Anyway, what you're saying is that _p_ does not
divide evenly n!/p. Why? Suppose that n >= 2p; then it is not true that
_p_ does divide evenly n!/p.

You're right. Can I get a hint for a good way to do this proof.

Sure. Instead of working with the greatest prime which divides _n_, work
with the greatest power of 2 which divides _n_.

Best regards,

Jose Carlos Santos
Back to top
Google
Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Sat Jan 10, 2009 1:46 am | All times are GMT
Forum index » Science and Technology » Math » Undergraduate
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts about uni. continuous proof bill Math 1 Tue Jul 18, 2006 10:30 pm
No new posts (humor) Another hand-waving incredibl... DGoncz@aol.com Math 0 Fri Jul 14, 2006 7:50 pm
No new posts Any Integer with the sum of its' divi... Dan Math 12 Fri Jul 14, 2006 5:20 am
No new posts Question about Cantor's proof Math1723 Math 53 Tue Jul 11, 2006 3:04 pm
No new posts Attempts to Refute Cantor's Uncountab... Hatto von Aquitanien Math 274 Sat Jul 08, 2006 8:06 am

Credit Cards | Cell Phones | Bad Credit Credit Card | Proxy | Loan
Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums


Powered by phpBB © 2001, 2005 phpBB Group

[ Time: 0.4922s ][ Queries: 16 (0.4066s) ][ GZIP on - Debug on ]