3
$\begingroup$

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?

3 Answers 3

7

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, or
  • $a+b=c+d$ and $b.

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

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. There are also $q-1$ fractions $a/b$ such that $a+b=p+q$ and $b, 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.

  • 1
    I still don't get why we are summing $\sum\limits_{k=2}^{p+q-1}k-1$How does summing the fractions have anything to do with counting the sequence number the fraction is in...2017-04-30
1

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.

0

Try induction on n with n = p + q.