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:
1/(1x3) + 1/(2x3)
1/(1x4) + 1/(2x3) (no 1/(2x4) because 2 and 4 is not relatively prime) + 1/(3x4)
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:
1/(1x6) + 1/(2x5) + 1/(3x4) + 1/(3x5) + 1/(4x5) + 1/(5x6)
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 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