Show that $p/q$ is the$ [(1/2)(p+q-1)(p+q-2)+q]$th term of the series

Question

I am attempting to prove that given a series of rational numbers $p/q$ as presented below: $$ 1/1,\; 2/1,\; 1/2,\; 3/1,\; 2/2,\; 1/3,\; 4/1,\; 3/2,\; 2/3,\; 1/4,\; \ldots $$

That $p/q$ is the $[(1/2)(p+q-1)(p+q-2)+q]$th term of the series.

I initially began attempting to construct the proof by induction, first setting $p=q=1$ and then $=q=n$ and so on, however, I was not able to get a solid answer.

Expanding the equation did not provide any helpful insights either.

I am wondering if anyone can provide any assistance?

Answer 1

Note that the sequence is ordered as follows: $\dfrac{a}b$ precedes $\dfrac{c}d$ in the sequence if and only if either

• $a+b<c+d$, or
• $a+b=c+d$ and $b<d$.

Thus, a fraction $p/q$ is preceded by all fractions $a/b$ such that $a+b<p+q$ and by all fractions $a/b$ such that $a+b=p+q$ and $b<q$.

There is one fraction $a/b$ such that $a+b=2$; there are two such that $a+b=3$; and in general there are $k-1$ fractions $a/b$ such that $a+b=k$. Thus, there are

$$\sum_{k=2}^{p+q-1}(k-1)=\sum_{i=1}^{p+q-2}i=\frac{(p+q-2)(p+q-1)}2\tag{1}$$

fractions $a/b$ such that $a+b<p+q$. There are also $q-1$ fractions $a/b$ such that $a+b=p+q$ and $b<q$, one for every value of $b$ from $1$ through $q-1$. Adding that to the subtotal $(1)$, we find that $p/q$ is preceded by

$$\frac{(p+q-2)(p+q-1)}2+(q-1)$$

terms and is therefore the

$$\left(\frac{(p+q-2)(p+q-1)}2+q\right)\text{-th}$$

term of the sequence, counting $1/1$ as the first term.

Answer 2

Try induction on n with n = p + q.

Answer 3

Observe that the set $\{2/1, 1/2\}$ contains the second and third term of the sequence, the sum of their nominator and denominator is 3, $\{3/1, 2/2, 1/3\}$, contains 3 elements, the sum is 4. $\{4/1, 3/2, 2/3, 1/4\}$, contains 4 elements, the sum is 5. So by induction, $p/q$ belong to the set which contains $p+q-1$ elements, the sum of each element's nominator and denominator is $p+q$. The number of elements in the sequence before this set is $(1+(p+q-2))(p+q-2)/2$, and $p/q$ is the $q$th term in the sequence $(p+q-1)/1, (p+q-2)/2,...1/(p+q-1).$ So the answer follows.