Introduction To The Sequence

Let us define the sequence as \(\{a_n\}_{n=1}^{\infty}\) , where \(a_n = \frac{p}{q}\) , \(p, q \in \mathbb{Z^+}\) , and

So, the initial few terms of the sequence are:

This formula provides a mapping from the set of ordered pairs of positive integers, \(\mathbb{Z}^+ \times \mathbb{Z}^+\), to the set of positive integers \(\mathbb{Z}^+\). By assigning each pair \((p,q)\) to a term \(a_n = p/q\), the sequence defines a surjection onto the set of positive rational numbers, \(\mathbb{Q}^+\). A key consequence of this is that the set \(\mathbb{Q}^+\) is countable.

It is important to note that, interestingly enough, in this series every rational number is repeated indefinitely. Thus \(1\) occurs as \(\frac{1}{1},\frac{2}{2},\frac{3}{3},\cdots\).We can, of course, avoid this by omitting every number which has already occurred in a simpler form, but then the problem of determining the precise position of \(p/q\) becomes more complicated.

We prove the formula in equation(1) as follows,

A More Of A Visual Explanation

In the sequence described by equation(2), we observe that the numerators \(p\) and denominators \(q\) follow a specific pattern, which can be visualised in the following table:

To select a particular numerator p and its corresponding denominator q, follow these rules:

1. Begin by counting the columns from left to right, followed by counting the rows from top to bottom, in both tables.
2. To find the n-th element (e.g., n=8 ), we count through the sequence according to rule 1 until we reach nth position. For n=8 , we discover that q=2 and p=3(as shown in the animation above).

Let \(a\) and \(b\) denote the row and column indices of the table, respectively. The tables follow the following formulas;

It is up to the readers to verify this. If you substitute \(a = p + q - 1\) and \(b = q\) into the equation \(b = \frac{a(1 - a)}{2} + n\), you will arrive at the required equation (1).

I will conclude this discussion, as this step is highly intuitive, and I encourage readers to engage with their own intuition in this matter.

The following table helps to visualize how we enumerate fractions diagonally, based on constant p + q values:

Interactive Diagonal Enumerator

We move anti-diagonally, where the sum p + q remains constant on each diagonal:

• Diagonal 2 (p+q=2): 1/1
• Diagonal 3 (p+q=3): 2/1, 1/2
• Diagonal 4 (p+q=4): 3/1, 2/2, 1/3
• Diagonal 5 (p+q=5): 4/1, 3/2, 2/3, 1/4

To find the nth term of the sequence, use:

Where:

• x is the diagonal number (total number of steps to reach the diagonal)
• y helps extract the denominator q
• Then compute p = x - q + 1 (since x = p + q - 1)

Steps to find the nth term from the table:

1. Compute x using the ceiling formula for the diagonal index
2. Calculate q = y = \( \frac{x(1 - x)}{2} + n \)
3. Then calculate p = x - q + 1
4. The nth term is then: aₙ = p/q

Intuitive Explanation

The formula in Equation(1) works by traversing the anti-diagonals of an infinite grid of fractions. The sequence is constructed by grouping terms where the sum of the numerator and denominator, \(p+q\), is constant.

• Group 1 (\(p+q=2\)): \(\frac{1}{1}\)
• Group 2 (\(p+q=3\)): \(\frac{2}{1}, \frac{1}{2}\)
• Group 3 (\(p+q=4\)): \(\frac{3}{1}, \frac{2}{2}, \frac{1}{3}\)
• Group 4 (\(p+q=5\)): \(\frac{4}{1}, \frac{3}{2}, \frac{2}{3}, \frac{1}{4}\)

The term \(\frac{(p+q-2)(p+q-1)}{2}\) is simply the formula for the \((p+q-2)\)-th triangular number, which counts the total number of elements in all the preceding groups. The term `\(+q\)` then specifies the position within the current group. This visual method suggests that every pair \((p,q)\) will eventually be reached. We will now prove this formally.

Formal Proof

The proof consists of two parts. First, we show that every positive rational number appears at least once. Second, we extend this to show that every rational number appears infinitely many times.

Part 1: Every Positive Rational Number Appears in the Sequence

Claim: For any positive rational number \( \frac{x}{y} \), where \( x, y \in \mathbb{Z}^+ \), there exists a positive integer \( n \) such that \( a_n = \frac{x}{y} \).

Proof by Construction:

1. Let \( \frac{x}{y} \) be an arbitrary positive rational number.
2. We construct a corresponding index \( n \) by choosing \( p=x \) and \( q=y \) and substituting them into Equation (1):
   \[ n = \frac{(x+y-2)(x+y-1)}{2} + y \]
3. We must verify that this \( n \) is a positive integer. Since \( x \ge 1 \) and \( y \ge 1 \), the term \( (x+y-2)(x+y-1) \) is a product of two consecutive integers, which is always even and thus divisible by 2. The result is a non-negative integer. Since \( y \ge 1 \), \( n \) is the sum of a non-negative integer and a positive integer, which is always a positive integer.
4. By this construction, the \(n\)-th term of the sequence is \( a_n = \frac{p}{q} = \frac{x}{y} \).

Since we can find a valid index \( n \) for any arbitrary rational \( \frac{x}{y} \), we have proven that every positive rational number appears at least once.

Part 2: Every Positive Rational Number Appears Infinitely Often

Claim: Any positive rational number appears at an infinite number of distinct positions in the sequence.

Proof:

1. Let \( \frac{x}{y} \) be an arbitrary positive rational number. This number has an infinite number of equivalent representations given by the set of ordered pairs:
   \[ S = \{ (kx, ky) \mid k \in \mathbb{Z}^+ \} = \{ (x,y), (2x,2y), (3x,3y), \dots \} \]
2. From Part 1, we know that for any ordered pair of positive integers \( (p,q) \), there exists a unique positive integer \( n \) corresponding to it.
3. For each pair \( (p_k, q_k) = (kx, ky) \) in the set \( S \), there is a corresponding unique index \( n_k \):
   \[ n_k = \frac{(k(x+y)-2)(k(x+y)-1)}{2} + ky \]
4. These indices \( n_k \) are all distinct. As \( k \) increases, the sum \( p_k+q_k = k(x+y) \) strictly increases, which in turn makes \( n_k \) strictly increase. Therefore, if \( k_1 \neq k_2 \), then \( n_{k_1} \neq n_{k_2} \).
5. The term at each of these distinct positions is \( a_{n_k} = \frac{p_k}{q_k} = \frac{kx}{ky} = \frac{x}{y} \).

Since we can find a distinct position \( n_k \) for every positive integer \( k \), we have proven that every positive rational number appears infinitely many times in the sequence.