Verified answer

Let's define for simplicity L(n; a) to denote the number of integers j <= n such that a_j is in [0, a]. Furthermore, let N(n) = n(n-1)/2.

Lemma 1: If l(n; a) denotes the number of integers j <= n s.t. a_j < a, then l(N(n); a) = N(n) - L(N(n); 1-a).

Proof: a_j < a <=> 1-a_j > 1-a <=> ~(1-a_j <= 1-a)

If we look at N(n) first terms for any n, all fractions p/q for 0 < p < q <= n are there. For each p/q, there is a corresponding (q-p)/p. The number or j | 1-a_j <= 1-a is therefore the same as the number of j | a_j <= 1-a, which is L(N(n); 1-a), but according to the introducing line, N(n) - l(N(n); a). QED.

Now clearly N(N(n); a, b) = L(N(n); b) - l(N(n); a) = L(N(n); b) + L(N(n); 1-a) - N(n). Let's prove that lim L(N(n); a)/N(n) = a, this would imply lim N(N(n); a, b)/N(n) = b - a (but note this is only a subsequence!)

Lemma 2: Let 0 <= a < 1. Then lim L(N(n); a)/N(n) = a.

Proof: We'll use the Cauchy-Stolz lemma:

L(N(n+1); a) - L(N(n); a) = #{p | 0<p<n+1, p/(n+1) <= a} = [(n+1)a], where [x] is the integer part of x.

This holds for a < 1, for a = 1, it is n.

N(n+1) - N(n) = n(n+1)/2 - n(n-1)/2 = n > 0, as the lemma needs

lim (L(N(n+1); a) - L(N(n); a))/n = lim [(n+1)a]/n = a

This has validity extended back to all a in [0, 1].

By the C-S lemma, this implies that lim L(N(n); a)/N(n) = a. QED.

This proves the question for a subsequence given by index sequence N(n). Let's show its validity for each the whole sequence:

Theorem: Limit of N(n; a, b)/n as n approaches +infinity is equal to b-a.

Proof: Let's find a decomposition n = N(k)+l such that 0 <= l < k (so that k is the greatest possible to make l nonnegative). Then

N(n; a, b) = N(N(k); a, b) + #{p integer | 0 <= p < k, p/(k+1) in [a, b]}

N(N(k); a, b) <= N(n; a, b) < N(N(k)+k; a, b) = N(N(k+1); a, b)

N(N(k); a, b)/n <= N(n; a, b)/n < N(N(k+1); a, b)/n

N(k)/n * N(N(k); a, b)/N(k) <= N(n; a, b)/n <= N(k+1)/n * N(N(k+1); a, b)/N(k+1)

Lemma 3: Let k(n) and l(n) build up the indicated decomposition n = N(k(n)) + l(n) for each n. Then both the limits of N(k(n))/n and of N(k(n)+1)/n as n approaches +infinity are 1.

Proof: Let's have a look at the reciprocal value of the first:

n/N(k(n)) = 1 + (n-N(k(n)))/N(k(n))

|n/N(k(n)) - 1| = (n-N(k(n)))/N(k(n))

n - N(k(n)) = l(n) < k(n)

As n tends to +infinity, so does k(n) and k(n)/N(k(n)) tends to zero.

The second limit is analogous. QED.

Continuation of the proof of the Theorem:

Both border sides of the inequality have a limit for n approaching +infinity. Let's plug it in to get

1 * (b-a) <= liminf N(n; a, b) <= limsup N(n; a, b) <= 1 * (b-a)

Since the left and right expressions are the same, N(n; a, b) must have a limit of b-a. QED.

The problem is intuitively simple, but it's so hard to be mathematically exact... I hope I did not make any big mistakes, I have not prepared this on paper and wrote my ideas directly to the window.