Summing Fractions

3 Dec 2011

Given an integer n > 1, the sum of 1 / (pq) for all p,q that 0 < p < q <= n and p + q > n and p,q is relatively prime is equal to 1/2

The first thing to notice is that we have to prove for all n.

Let's first try a few example:

n=2

1/(1x2)

n=3

1/(1x3) + 1/(2x3)

n=4

1/(1x4) + 1/(2x3) (no 1/(2x4) because 2 and 4 is not relatively prime) + 1/(3x4)

n=5

1/(1x5) + 1/(2x5) + 1/(3x4) + 1/(3x5) + 1/(4x5)

We can generalize a little.

For n, it must contain 1/n and 1/((n-1)xn). Coincidentally, 1/n + 1/((n-1)xn) = 1/(n-1).

And For n, it must contain 1/((n-2)x(n-1)) if n >= 4.

Please note that (n-1) and (n-2) is guaranteed to be relatively prime and (n-1)+(n-2) > n if n >= 4.

Therefore, 1/n + 1/((n-1)xn) + 1/((n-2)x(n-1)) = 1/(n-2).

I still don't see any pattern. Let's try a few more cases:

n=6

1/(1x6) + 1/(2x5) + 1/(3x4) + 1/(3x5) + 1/(4x5) + 1/(5x6)

n=7

1/(1x7) + 1/(2x7) + 1/(3x5) + 1/(3x7) + 1/(4x5) + 1/(4x7) + 1/(5x6) + 1/(5x7) + 1/(6x7)

From n=7, 1/(1x7) + 1/(6x7) + 1/(5x6) + 1/(4x5) = 1/4.

And we have 1/(3x5) + 1/(2x7) + 1/(3x7) + 1/(4x7) + 1/(5x7) left.

I still cannot see any pattern out of it.

Probably we need to try another approach.

Let's try induction. If we move from n to (n+1), what is added and what is deleted?

For any (p,q) that p+q=(n+1), 1/pq is deleted. Conversely, we can add 1/(px(n+1)) + 1/(qx(n+1)) because p + (n+1) > n and q + (n+1) > n.

There are two things to prove:

  1. The terms that can be added on (n+1) must consist of (n+1)
  2. p and (n+1) and q and (n+1) are relatively prime.

The first one is relatively easy. If the term is 1/pr (r <= n), then it is valid in the step n. Therefore, every new term must consist of (n+1).

The second one is the difficult one. Can we really prove that p and (n+1) is relatively prime?

We know that p and q is relatively prime and p+q=(n+1).

I really wanna prove by contradiction and I don't know why… (Maybe because there is no other way to go)

Let's assume that p and (n+1) is not relatively prime. Therefore, there is x that divides p and (n+1).

This means that

xy + q = xz q = (xz - xy) = x(z-y)

Amazingly, it turns out that q must be divided by x also. It contradicts our assumption that p and q are relatively prime.

And the proof is complete. <3

Give it a kudos