SERVING THE QUANTITATIVE FINANCE COMMUNITY

sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### Alternating harmonic sum

Let integers m, n satisfy . Prove that m is a multiple of 2003.(This problem of course should have been posted 3 years ago...)

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

### Alternating harmonic sum

m = 187280139691754991954689696064673719711956788730199355005674805517848644623283\575956589582972941220749058108870240015721647317682809494503732310130055648879\961606413551481551869453347108706902962755469906099131479501769095352735649581\434239212808088032702745003389952703510255438779039702464445167161742840942360\397072142186643221015050354899119482884234567477313020919158418766023013624153\052523781373052284463525342140321762861105335532913216523556739076565249604889\383299681215658737890725382784817644276785987211068931426756143567708362506258\690797803421251146398466511266510214481m / 2003 = 934998201157039400672439820592479878741671436496252396433723442425604815892579\011266048841602302649770634592462506319129542275001545154786481827908415620968\355498819528115585968314264147313544497031801827754026357971887645295734645938\263800363495197367462531220119584141339268291458011495079606426169460014689767\334359172174953674563406664498849140710107675872755970639832345312146847848991\774956472157025883492388128508845545986546857378498335115111028839566897677930\021466206768141477237770258536283795690394344538536851855996722754410197235440\29354869406515799499983280712186827, integer, QED.
Last edited by alexandreC on April 22nd, 2006, 10:00 pm, edited 1 time in total.

sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### Alternating harmonic sum

Great proof! Now I believe it myself

sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### Alternating harmonic sum

Anyone interested in getting a real proof?

Chukchi
Posts: 915
Joined: December 15th, 2001, 3:43 am

### Alternating harmonic sum

There is a nice theorem about divisibility of numerator of alternating harmonic sum.2003 is a prime p=6k-1 (k=334), then p divides a(4k-1)=a(1335).Ref: http://www.research.att.com/~njas/sequences/A097279
Last edited by Chukchi on April 23rd, 2006, 10:00 pm, edited 1 time in total.

sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### Alternating harmonic sum

Yes, it is the same statement. Still no proof though...

zarnywhoop
Posts: 337
Joined: December 2nd, 2004, 5:39 pm

### Alternating harmonic sum

What's wrong with the given proof? I guess one should show that the suggested numerator and denominator are coprime, but there's not much else to do.

sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### Alternating harmonic sum

QuoteOriginally posted by: zarnywhoopWhat's wrong with the given proof? I guess one should show that the suggested numerator and denominator are coprime, but there's not much else to do.Could there possibly be a bug in the given "proof"?In any case, the real problem is of course to find a proof that would also stand for any prime p = 6k-1, as Chukchi pointed out below.

mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

### Alternating harmonic sum

2003 is prime. Multiply numerator and denominator by 2003!, you get that the denominator is not divisible by 2003, and the numerator is a sum of terms of the form (-1)^k 2003!/k, where k<=1335. All of these terms are divisible by 2003, hence the numerator is divisible by 2003. QED.

mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

### Alternating harmonic sum

Sorry, meant 1335!

sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### Alternating harmonic sum

QuoteOriginally posted by: mattcushman2003 is prime. Multiply numerator and denominator by 2003!, you get that the denominator is not divisible by 2003, and the numerator is a sum of terms of the form (-1)^k 2003!/k, where k<=1335. All of these terms are divisible by 2003, hence the numerator is divisible by 2003. QED.Why the denominator is not divisible by 2003?Wouldn't this argument hold for any other prime imaginable? Or any other bound (besides 1335), for that matter? P.S. Sorry, crossed with your later post...
Last edited by sevvost on April 23rd, 2006, 10:00 pm, edited 1 time in total.

mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

### Alternating harmonic sum

Nevermind.. just realized my "proof" is erroneous. Needs more work on the numerator...

wannabequantie
Posts: 70
Joined: October 30th, 2004, 12:13 pm

### Alternating harmonic sum

Hi,Heres a solution to the problem. In what follows i'm going to be working in the field , so when i write a = b i mean of course a=b modulo(2003) and when i write 1/a I mean the inverse of a in this field F. Now note that 1 + 1/2 + 1/3 + ... 1/2002 = 0 since this is the same as the set of numbers 1, 2, 3 ... 2002 under some permutation. Also 1/(2003-a) = -1/a. Now let A = 1 - 1/2 + 1/3 ... 1/1335 = (1-1/2+1/3...1/1335) + (1+1/2+1/3+...1/2002)= 2(1 + 1/3 + 1/5 +... 1/1335) + (1/1336 + ... 1/2002)= 2(1 + 1/3 + 1/5 +... 1/1335) - (1/667 + ... 1)= 2(1 + 1/3 + 1/5 + ...1/1335) - 2(1/2 + 1/4 + ...1/1334)= 2(1 - 1/2 + 1/3 - 1/4 ... 1/1335) = 2A.So now since we have A = 2A therefore A has to be equal to zero! QED.I have left some details to be filled but i assume anyone reading this should be able to fill that in.Ofcourse note that this method is quite general and you can use the same proof for any prime of the form 3n - 1 instead of 2003.

pk14
Posts: 85
Joined: February 15th, 2006, 12:43 am

### Alternating harmonic sum

Dear wannabequantie,very nice proof!!! Awesome!!!BTW, are you one of those who came to quant with a Math Ph.D.?

sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### Alternating harmonic sum

Yes, this is correct. Here is a "naive" version of the same solution.m/n = 1 -1/2 + 1/3 - ...- 1/1334 + 1/1335 = (1 + 1/2 + 1/3 +...+ 1/1334 + 1/1335) - 2(1/2 + 1/4 + ... + 1/1334) = 1/668 + 1/669 + ... + 1/1335.Now, grouping terms in pairs in a school kid Gauss manner (conveniently, we have an even number of terms), we have:m/n = (1/668 + 1/1335) + (1/669 + 1/1334) + ... + (1/1001 + 1/1002) and the result follows from each term being equal 2003/q where q = k(2003-k) is relatively prime to 2003.