Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Try induction on n with n = p + q.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.