Counting Positive Rational Numbers
Date: 09/09/2001 at 15:43:35 From: Alfred Lauzon Subject: Counting the positive rational numbers In Hardy's book _Pure Mathematics_, on p. 1, he gives a formula for counting the positive rational numbers p/q when they are arranged in a triangular matrix and counted down diagonally from the top row, resulting in the series 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, ... Then p/q is the [1/2(p+q-1)(p+q-2)+q]th term of the series. I can see that the formula does work for the few numbers I've tried, but how can it be proved for all such numbers?
Date: 09/10/2001 at 15:22:23 From: Doctor Peterson Subject: Re: Counting the positive rational numbers Hi, Alfred! This is the sort of thing that is "obvious" if you are looking at it the right way. If we make a chart of the index in this sequence, we have \p| q \| 1 2 3 4 5 ----+--------------- 1 | 1 2 4 7 11 2 | 3 5 8 12 3 | 6 9 13 4 |10 14 5 |15 and so on. We are making a sequence of diagonal rows, each of which ends (at the lower left) with the triangular number T[n], where n is the row number (1 for the first row, containing only "1"), and T[n] = n(n+1)/2 The fraction p/q is in row number p+q-1; for instance, to get to 3/2 from 1 we go down two rows and across 1 more, making a total of 3 rows away from row 1: (3-1)+(2-1)+1 = 4. The previous row, row p+q-2, ends with T[p+q-2]; in my example this is the 6 at the end of row 3. Now we have to add q to this index to get to the entry for p/q in the next row: 6 + 2 = 8 gives us the index for 3/2. In general, the index for p/q is T[p+q-2] + q = (p+q-2)(p+q-1)/2 + q And that's what Hardy probably saw immediately, and expects us to see, too. (I don't have the book; I assume he does something about the fact that this count doesn't take into account equivalent fractions.) - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum