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:

- The terms that can be added on (n+1) must consist of (n+1)
- 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