Kind of an interesting one....

Originally posted by Acolyte
Now I'm confused. Why not count the number of d-denominator rationals in (0,N]? Also, why not set N=1, if it saves confusion?

I suppose one could set N=1, except that S is a function of d and N. The idea was suggested by Farey sequences. Let P be the totient function I mentioned earlier, and F(d) be the set of rationals with denominator at most d. Then clearly there are 1 + SUM(k=1 to d) P(k) elements of F(n) in [0,1]. But:

1 + SUM(k=1 to d) P(k) = 1 + SUM(k=1 to d) k*PROD(p|k)(1-1/p) = 1 + SUM(k=1 to d) S(k;k)

where S(k;k) is the S(k) we have been using all along with N=k. Say d is even. Now take k = 1, 3, 5,...d/2 - 1. Since S(k;k) = 2S(2k;k) and S(2k; 2k) = 2S(2k;k), we note that there are the same number of even-denom rats. with k = 2,4,6,8,...d as there are odd-denom rats. in k=1,3,5,7,9,...d/2-1, and thus there tend to be twice as many odd denom rats as even denom. rats. I saw another proof in an old number theory book once that used a variant of this idea.