# Show that the sequence $\frac{0}{1}, \frac{0}{2}, \frac{1}{2}, \frac{0}{3}, \frac{1}{3}, \frac{2}{3}, \dots \frac{k-1}{k}$ is equidistributed mod 1

I need to show that the sequence $$\frac{0}{1}, \frac{0}{2}, \frac{1}{2}, \frac{0}{3}, \frac{1}{3}, \frac{2}{3}, \dots , \frac{0}{k}, \frac{1}{k}, \dots , \frac{k-1}{k}$$ is equidistributed in the interval $$[0,1]$$ (and so equidistributed mod $$1$$).

Ah, of course I can't use any further theorem developped in the theory of equidistibution of sequences like, for example, Weyl 's criterion. I must deduce it from the definition.

This is taken from Kuipers and Niederreiter, exercize 1.13. I found this old question but as you can see noone answered it. Thank you in advance

Let $$(x_n)_{n \geq 0}$$ be this sequence. We want to show that, for any function $$f \in \mathcal{C} ([0,1], \mathbb{R})$$,

$$\lim_{n \to + \infty} \frac{1}{n} \sum_{k=0}^{n-1} f(x_k) = \int_0^1 f(t) \ \text{d}t.$$

The sequence is a concatenation of finite subsequence $$(k/n)_{0 \leq k < n}$$. We shall proceed in three steps: first by proving convergence for these subsequences, the for the initial sequence $$(x_n)_{n \geq 0}$$ along a nice subsequence, and then the equidistribution.

Let $$f \in \mathcal{C} ([0,1], \mathbb{R})$$.

First step

We have

$$\lim_{n \to + \infty} \frac{1}{n} \sum_{k=0}^{n-1} f(k/n) = \int_0^1 f(t) \ \text{d}t,$$

since the left ahnd-side is a Riemann sum for $$f$$. We write $$u_n$$ for the $$n$$th Riemann sum $$\frac{1}{n} \sum_{k=0}^{n-1} f(k/n)$$.

Second step

Let $$N \geq 0$$, and set $$n(N) := \frac{N(N+1)}{2}$$. Then

$$\frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) = \frac{2}{N(N+1)} \sum_{\ell = 1}^N \sum_{k=0}^{\ell-1} f(k/\ell) = \sum_{\ell = 1}^N \frac{2\ell}{N(N+1)} u_\ell.$$

Set $$v_\ell^{(N)} := \frac{2\ell}{N(N+1)}$$ for $$\ell \leq N$$, and $$0$$ for $$\ell \geq N+1$$. Then

$$\frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) = \sum_{\ell = 1}^{+ \infty} v_\ell^{(N)} u_\ell.$$

• $$\sum_{\ell=1}^{+\infty} v_\ell^{(N)} = 1$$ for all $$N$$,

• $$\lim_{M \to + \infty} \sum_{\ell=1}^{M} v_\ell^{(N)} = 0$$,

• $$\lim_{\ell \to + \infty} u_\ell = \int_0^1 f(t) \ \text{d}t$$.

Hence, by a lemma I'll leave aside (but can be proved with some $$\epsilon$$-$$\delta$$ arguments),

$$\lim_{N \to + \infty} \frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) = \lim_{N \to + \infty} \sum_{\ell = 1}^{+ \infty} v_\ell^{(N)} u_\ell = \int_0^1 f(t) \ \text{d}t.$$

Third step

Let $$n \geq 0$$. Let $$N$$ be the largest integer such that $$\frac{N(N+1)}{2} \leq n$$. Then $$n-n(N) \leq n(N+1)-n(N) = N+1 \leq \sqrt{2(n+1)}$$, so that

$$\frac{1}{n} \sum_{k=0}^{n-1} f(x_k) = \frac{n(N)}{n} \frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) + \frac{1}{n} \sum_{k=n(N)}^{n-1} f(x_k) = (1+o(1)) \frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) + O\left(\frac{\|f\|_{\infty}}{\sqrt{n}} \right),$$

and thus the full sequence also converges to the integral of $$f$$.