n > 2 is an integer. Consider the pairs (a, b) of relatively prime positive integers, such that a < b ≤ n and a + b > n. Show that the sum of 1/ab taken over all such pairs is 1/2.
Solution
Induction on n. It is obvious for n = 3, because the only pairs are (1, 3) and (2, 3), and 1/3 + 1/6 = 1/2. Now suppose it is true for n. As we move to n+1, we introduce the new pairs (a, n+1) with a relatively prime to n+1 and we lose the pairs (a, n+1-a) with a relatively prime to n+1-a and hence to n+1. So for each a relatively prime to n+1 and < (n+1)/2 we gain (a, n+1) and (n+1-a, n+1) and lose (a, n+1-a). But 1/a(n+1) + 1/( (n+1-a)(n+1) ) = ( n+1-a + a)/( a(n+1-a)(n+1) ) = 1/( a(n+1-a) ).
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 2000